|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Есть "отрезок" от 1 до 100. Есть набор данных с "координатами" на этом отрезке типа: начало конец 1 10 9 15 7 30 60 100 Как мне по быстрому определить что в диапазоне 31-59 данных нет? На малых "отрезках" можно просто перебором, но когда отрезок размером десятки тысяч и набор данных содержит тоже тысячи диапазонов - всё стопорится. Может есть у кого какие идеи? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 11:33 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Сейчас делаю примерно так: Добавляю все отсчеты отрезка в коллекцию Код: vbnet 1. 2. 3. 4. 5.
Далее удаляю все занятые отрезки из коллекции Код: vbnet 1. 2. 3. 4. 5. 6. 7. 8. 9.
В итоге в коллекции остаются пустоты отрезка. Но на больших отрезках это работает очень долго. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 12:30 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Задача, в принципе, классическая. Но наиболее быстрый алгоритм будет зависеть от нескольких факторов. Например, что вы желаете получить в итоге? Список "пустот" в виде отрезков? Список "заполненных" отрезков? Список точек последовательности "занято-незанято"? Еще вопрос - параметры "отрезков" это дискретные значения (например, координаты - всегда целые числа) или непрерывные? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 13:34 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, В итоге мне надо получить список пустот с координатами начала и конца пустоты. Список заполненных отрезков у меня есть. Параметры отрезков - дискретные. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 13:43 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, Извиняюсь, не правильно написал. Параметры отрезков - непрерывная величина. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 13:58 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Пока посмотрите http://www.sql.ru/forum/actualthread.aspx?tid=901998 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 14:07 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, Спасибо. Похоже на мою задачу. Попробую понять. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 14:27 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, Читал-читал я ту тему, пробовал по всякому. Остановился сейчас на варианте с массивом, задаю массиву размер отрезка и заполняю его единичками из наборов. Потом пробегаюсь по массиву и смотрю где нолик-там свободно. Но кажется что проще как то можно((( ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 19:36 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Что-то вроде Код: 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.
Мелкие ляпы поправь и добавь обработку случая, когда дыр нет (лучше превратить в функцию). ... |
|||
:
Нравится:
Не нравится:
|
|||
13.06.2012, 23:13 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Посмотрите пример... Там первый-второй тесты - это решения через массив значений координат, различие только в типе данных точки (первый - "парные" значения и использование знака числа для учета "веса", второй - использование UDT для точки); третий тест - решение через "объединение отрезков" с инверсией. Не забывайте генерировать список координат! Ну и Selection-сортировку можно заменить на QuickSort... ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 00:03 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Akina, Спасибо. Но типы данных такие как snippet и синтаксис мне не знаком( Это .NET что ли? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 09:01 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, Спасибо. Сейчас посмотрю, разберусь что к чему. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 09:03 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Найти пустоты на отрезке, автор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 ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 11:00 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Найти пустоты на отрезкетипы данных такие как snippet обычная структура из двух компонентов. Код: vbnet 1. 2. 3. 4.
Найти пустоты на отрезкесинтаксис мне не знаком( Это .NET что ли?Basic ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 11:15 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
В смысле Visual Basic (скажем, 6.0) ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 11:23 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Спасибо всем за участие. Задействовал "третий тест" от AndreTM. Быстродействие устраивает. Akina - Ваш код тоже опробую на быстродействие и отпишусь. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 11:33 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Нашел я глюк в своем третьем тесте... Поправил по-быстрому ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 11:39 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, Что то Вы меня с понталыки сбили совсем! Начал проверять на простейших примерах и получаю не правильные данные. Короче возвращаюсь к своему методу что бы не наступить на чужие грабли. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 12:58 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Найти пустоты на отрезкеВаш код тоже опробую на быстродействие и отпишусь. Не забудьте только написать (или взять готовые) функции сортировки и выбора максимального... ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 13:15 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Для дополнительного ускорения - разумнее сразу зарезервить free как 1+ubound(occupied) и хранить счётчик найденных дыр. В конце процедуры один раз изменить размер к актуальному. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 13:41 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Найти пустоты на отрезкеНачал проверять на простейших примерах и получаю не правильные данные.Дайте пример ваших "простейших" данных, где получаются "ошибки". А то я на слово не верю... И еще - на этих данных получается ошибочный результат по обоим алгоритмам? ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 14:10 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
AndreTM, Извиняюсь, исправленный вариант работает без ошибок в Excel. Я данные беру не с листа книги а из массивов Option Base 0. Вот пытаюсь распутать эти i,j,k)) ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 14:27 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
Найти пустоты на отрезкеВот пытаюсь распутать эти i,j,k))ICQ и Skype есть в профиле... ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 14:31 |
|
Найти пустоты на отрезке
|
|||
---|---|---|---|
#18+
В аттаче - демка. На VB6, проверил вроде на всех краевых, не ошибается. Только требует соблюдения end>=start. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.06.2012, 15:43 |
|
|
start [/forum/topic.php?fid=60&msg=37837932&tid=2157679]: |
0ms |
get settings: |
15ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
27ms |
get topic data: |
14ms |
get forum data: |
2ms |
get page messages: |
64ms |
get tp. blocked users: |
1ms |
others: | 281ms |
total: | 428ms |
0 / 0 |