Гость
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Найти пустоты на отрезке / 25 сообщений из 25, страница 1 из 1
13.06.2012, 11:33
    #37836052
Найти пустоты на отрезке
Есть "отрезок" от 1 до 100.
Есть набор данных с "координатами" на этом отрезке типа:
начало конец
1 10
9 15
7 30
60 100
Как мне по быстрому определить что в диапазоне 31-59 данных нет?
На малых "отрезках" можно просто перебором, но когда отрезок размером десятки тысяч и набор данных содержит тоже тысячи диапазонов - всё стопорится.
Может есть у кого какие идеи?
...
Рейтинг: 0 / 0
13.06.2012, 12:30
    #37836163
Найти пустоты на отрезке
Сейчас делаю примерно так:
Добавляю все отсчеты отрезка в коллекцию
Код: vbnet
1.
2.
3.
4.
5.
Dim cC as new Collection

For i=1 to длина отрезка Step iStep
  cC.Add i, CStr(i)
next i


Далее удаляю все занятые отрезки из коллекции

Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
For i=1 to Количество наборов данных
      For i2=cC.count to 1 Step 1
            if cC.Item(i2)>набор_данных(i).начало and if cC.Item(i2)<набор_данных(i).конец then

                cC.Remove (i2)
            end if
      next i2

next i


В итоге в коллекции остаются пустоты отрезка.
Но на больших отрезках это работает очень долго.
...
Рейтинг: 0 / 0
13.06.2012, 13:34
    #37836265
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Задача, в принципе, классическая. Но наиболее быстрый алгоритм будет зависеть от нескольких факторов.
Например, что вы желаете получить в итоге? Список "пустот" в виде отрезков? Список "заполненных" отрезков? Список точек последовательности "занято-незанято"? Еще вопрос - параметры "отрезков" это дискретные значения (например, координаты - всегда целые числа) или непрерывные?
...
Рейтинг: 0 / 0
13.06.2012, 13:43
    #37836290
Найти пустоты на отрезке
AndreTM,

В итоге мне надо получить список пустот с координатами начала и конца пустоты.
Список заполненных отрезков у меня есть.
Параметры отрезков - дискретные.
...
Рейтинг: 0 / 0
13.06.2012, 13:58
    #37836319
Найти пустоты на отрезке
AndreTM,

Извиняюсь, не правильно написал.
Параметры отрезков - непрерывная величина.
...
Рейтинг: 0 / 0
13.06.2012, 14:07
    #37836337
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
...
Рейтинг: 0 / 0
13.06.2012, 14:27
    #37836372
Найти пустоты на отрезке
AndreTM,

Спасибо.
Похоже на мою задачу.
Попробую понять.
...
Рейтинг: 0 / 0
13.06.2012, 19:36
    #37836861
Найти пустоты на отрезке
AndreTM,

Читал-читал я ту тему, пробовал по всякому.
Остановился сейчас на варианте с массивом, задаю массиву размер отрезка и заполняю его единичками из наборов. Потом пробегаюсь по массиву и смотрю где нолик-там свободно.
Но кажется что проще как то можно(((
...
Рейтинг: 0 / 0
13.06.2012, 23:13
    #37837013
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Что-то вроде
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
sub getholes(whole as snippet, occupied() as snippet, free() as snippet)
redim free(0)
dim tmp as snippet
occupied=qsort(occupied) ' сортировка по началу
redim free(0)
if whole.start <> occupied(0).start then
  free(0).start = whole.start 
  free(0).end = occupied(0).start 
  redim preserve free(1+ubound(free))
end if
tmp.start = occupied(0).start 
tmp.end = occupied(0).end 
for i = 1 to ubound(occupied)
  if occupied(i).start <= tmp.end then
    tmp.end = max(occupied(i).end, tmp.end)
  else
    free(ubound(free)).start = tmp.end 
    free(ubound(free)).end = occupied(i).start 
    redim preserve free(1+ubound(free))    
  end if
next
if tmp.end < whole.end then
  free(ubound(free)).start = tmp.end 
  free(ubound(free)).end = whole.end  
endif
end sub


Мелкие ляпы поправь и добавь обработку случая, когда дыр нет (лучше превратить в функцию).
...
Рейтинг: 0 / 0
14.06.2012, 00:03
    #37837038
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Посмотрите пример...
Там первый-второй тесты - это решения через массив значений координат, различие только в типе данных точки (первый - "парные" значения и использование знака числа для учета "веса", второй - использование UDT для точки); третий тест - решение через "объединение отрезков" с инверсией.
Не забывайте генерировать список координат!
Ну и Selection-сортировку можно заменить на QuickSort...
...
Рейтинг: 0 / 0
14.06.2012, 09:01
    #37837299
Найти пустоты на отрезке
Akina,

Спасибо.
Но типы данных такие как snippet и синтаксис мне не знаком(
Это .NET что ли?
...
Рейтинг: 0 / 0
14.06.2012, 09:03
    #37837301
Найти пустоты на отрезке
AndreTM,

Спасибо.
Сейчас посмотрю, разберусь что к чему.
...
Рейтинг: 0 / 0
14.06.2012, 11:00
    #37837484
ПЕНСИОНЕРКА
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Найти пустоты на отрезке,

авторFor i=1 to длина отрезка Step iStep
cC.Add i, CStr(i)
next i


какого типа длина отрезка(целое, дробное)
диапазон длин(до 32000, 320000,более)

п.с.прикидываю под свой прием макания
dim xm(0 to 32000) as long

xm(101)=1
for j=130 to 555
xm(j)=1
next for

''''поиск -одно макание
xm(101)=1
xm(102)=0
xm(220)=1
...
Рейтинг: 0 / 0
14.06.2012, 11:15
    #37837505
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Найти пустоты на отрезкетипы данных такие как snippet
обычная структура из двух компонентов.
Код: vbnet
1.
2.
3.
4.
Type snippet
start as double
end as double
end type



Найти пустоты на отрезкесинтаксис мне не знаком(
Это .NET что ли?Basic
...
Рейтинг: 0 / 0
14.06.2012, 11:23
    #37837518
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
В смысле Visual Basic (скажем, 6.0)
...
Рейтинг: 0 / 0
14.06.2012, 11:33
    #37837534
Найти пустоты на отрезке
Спасибо всем за участие.

Задействовал "третий тест" от AndreTM.
Быстродействие устраивает.

Akina - Ваш код тоже опробую на быстродействие и отпишусь.
...
Рейтинг: 0 / 0
14.06.2012, 11:39
    #37837549
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Нашел я глюк в своем третьем тесте... Поправил по-быстрому
...
Рейтинг: 0 / 0
14.06.2012, 12:58
    #37837734
Найти пустоты на отрезке
AndreTM,

Что то Вы меня с понталыки сбили совсем!
Начал проверять на простейших примерах и получаю не правильные данные.
Короче возвращаюсь к своему методу что бы не наступить на чужие грабли.
...
Рейтинг: 0 / 0
14.06.2012, 13:15
    #37837763
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Найти пустоты на отрезкеВаш код тоже опробую на быстродействие и отпишусь.
Не забудьте только написать (или взять готовые) функции сортировки и выбора максимального...
...
Рейтинг: 0 / 0
14.06.2012, 13:41
    #37837815
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Для дополнительного ускорения - разумнее сразу зарезервить free как 1+ubound(occupied) и хранить счётчик найденных дыр. В конце процедуры один раз изменить размер к актуальному.
...
Рейтинг: 0 / 0
14.06.2012, 14:10
    #37837891
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Найти пустоты на отрезкеНачал проверять на простейших примерах и получаю не правильные данные.Дайте пример ваших "простейших" данных, где получаются "ошибки". А то я на слово не верю...
И еще - на этих данных получается ошибочный результат по обоим алгоритмам?
...
Рейтинг: 0 / 0
14.06.2012, 14:27
    #37837926
Найти пустоты на отрезке
AndreTM,

Извиняюсь, исправленный вариант работает без ошибок в Excel.
Я данные беру не с листа книги а из массивов Option Base 0.
Вот пытаюсь распутать эти i,j,k))
...
Рейтинг: 0 / 0
14.06.2012, 14:31
    #37837932
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
Найти пустоты на отрезкеВот пытаюсь распутать эти i,j,k))ICQ и Skype есть в профиле...
...
Рейтинг: 0 / 0
14.06.2012, 15:43
    #37838087
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Найти пустоты на отрезке
В аттаче - демка. На VB6, проверил вроде на всех краевых, не ошибается. Только требует соблюдения end>=start.
...
Рейтинг: 0 / 0
14.06.2012, 15:50
    #37838102
Найти пустоты на отрезке
Akina,

Спасибо!
Работает)
...
Рейтинг: 0 / 0
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Найти пустоты на отрезке / 25 сообщений из 25, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]