powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Найти пустоты на отрезке
25 сообщений из 25, страница 1 из 1
Найти пустоты на отрезке
    #37836052
Есть "отрезок" от 1 до 100.
Есть набор данных с "координатами" на этом отрезке типа:
начало конец
1 10
9 15
7 30
60 100
Как мне по быстрому определить что в диапазоне 31-59 данных нет?
На малых "отрезках" можно просто перебором, но когда отрезок размером десятки тысяч и набор данных содержит тоже тысячи диапазонов - всё стопорится.
Может есть у кого какие идеи?
...
Рейтинг: 0 / 0
Найти пустоты на отрезке
    #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
Найти пустоты на отрезке
    #37836265
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задача, в принципе, классическая. Но наиболее быстрый алгоритм будет зависеть от нескольких факторов.
Например, что вы желаете получить в итоге? Список "пустот" в виде отрезков? Список "заполненных" отрезков? Список точек последовательности "занято-незанято"? Еще вопрос - параметры "отрезков" это дискретные значения (например, координаты - всегда целые числа) или непрерывные?
...
Рейтинг: 0 / 0
Найти пустоты на отрезке
    #37836290
AndreTM,

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

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

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

Читал-читал я ту тему, пробовал по всякому.
Остановился сейчас на варианте с массивом, задаю массиву размер отрезка и заполняю его единичками из наборов. Потом пробегаюсь по массиву и смотрю где нолик-там свободно.
Но кажется что проще как то можно(((
...
Рейтинг: 0 / 0
Найти пустоты на отрезке
    #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
Найти пустоты на отрезке
    #37837038
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Посмотрите пример...
Там первый-второй тесты - это решения через массив значений координат, различие только в типе данных точки (первый - "парные" значения и использование знака числа для учета "веса", второй - использование UDT для точки); третий тест - решение через "объединение отрезков" с инверсией.
Не забывайте генерировать список координат!
Ну и Selection-сортировку можно заменить на QuickSort...
...
Рейтинг: 0 / 0
Найти пустоты на отрезке
    #37837299
Akina,

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

Спасибо.
Сейчас посмотрю, разберусь что к чему.
...
Рейтинг: 0 / 0
Найти пустоты на отрезке
    #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
Найти пустоты на отрезке
    #37837505
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Найти пустоты на отрезкетипы данных такие как snippet
обычная структура из двух компонентов.
Код: vbnet
1.
2.
3.
4.
Type snippet
start as double
end as double
end type



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

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

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

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

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

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


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