ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Быстрое получение ID диапазона в которое входит число
15 сообщений из 15, страница 1 из 1
Быстрое получение ID диапазона в которое входит число
    #39094558
Eolt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Eolt
Участник
Есть отрезок случайной длинны, допустим от 0 до 100000 едениц. Он разбивается на N диапазонов, тоже случайного размера.
Каждый диапазон имеет уникальное сгенерированное название типа "ASWDVGDEDS".
Затем приходит случайное число от 0 до 100000, нужно вернуть название диапазона, в который входит эта точка и относительное расстояние от точки начала найденного диапазона.
Как реализовать такую задачу, чтобы название диапазона и точка в нем возвращались максимально быстро?
...
Рейтинг: 0 / 0
04.11.2015, 18:11
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094572
Bidgo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bidgo
Гость
Например, при разбивании отрезка генерировать 3-мерный массив - первая точка, последняя точка и название отрезка.
Затем в цикле проверять массив на принадлежность полученной точки..
Если точка больше первого элемента массива (первой точки отрезка) и меньше второго элемента (последней точки отрезка), возвращать 3-й элемент (название) и разницу между имеющейся точкой и первым элементом массива (то есть относительное расстояние от начала отрезка).
...
Рейтинг: 0 / 0
04.11.2015, 18:36
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094584
Eolt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Eolt
Участник
Bidgo,

тут проблема в том, что если будут тысячи диапазонов, надо делать тысячи проверок на принадлежность точки.
А хотелось бы как-то сразу получать, с минимальными затратами.
...
Рейтинг: 0 / 0
04.11.2015, 18:51
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094585
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Это-ж хэш-таблица!
...
Рейтинг: 0 / 0
04.11.2015, 18:53
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094587
Eolt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Eolt
Участник
hclubmkЭто-ж хэш-таблица!

поясни
...
Рейтинг: 0 / 0
04.11.2015, 18:54
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094591
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
Bidgo правильно подсказал, нужно построить индексированную таблицу, упорядочить ее по этим самым индексам, и искать бинарным поиском необходимый индекс/число
...
Рейтинг: 0 / 0
04.11.2015, 19:02
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094787
ZVI
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZVI
Участник
Для бинарного поиска достаточно 2-мерного массива, где в 1-й размерности будут значение конца отрезка, а во 2-й - имя соответствующего отрезка. Для нулевого значения N всегда возвращать имя первого отрезка: If N = 0 Then N = 1

Бинарный поиск достаточно быстрый, но быстрее будет, если создать 1-мерный массив с элементами от 0 до 100000, в которые записать название отрезка, соответствующее каждому значению. Тогда для значения N достаточно заглянуть во N-й элемент массива.
...
Рейтинг: 0 / 0
05.11.2015, 03:49
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094855
hclubmk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hclubmk
Участник
ZVI прекрасная идея ноEolt и относительное расстояние от точки начала найденного диапазона.поэтому массив двумерный, с индексом внутреннего смешения в диапазоне одинакового имени.
№инд смещимя10имя121имя132имя140имя250имя361имя370имя481имя492имя4 правда, такая такая таблица должна иметь размерность, равную количеству возможных чисел, а не количеству имен, но судя из первой строки условия, для ТС это не критично.
...
Рейтинг: 0 / 0
05.11.2015, 08:37
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094944
Eolt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Eolt
Участник
да идея норм, только вместо имени в таблице, надо хранить указатель на строку имени, чтобы уменьшить объем потребляемой памяти
...
Рейтинг: 0 / 0
05.11.2015, 09:59
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39094954
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Eoltесли будут тысячи диапазонов, надо делать тысячи проверок на принадлежность точки.
От 10 до 14 проверок. Если диапазоны хранить в виде массива (начало-конец-имя), сортированного по началу.
...
Рейтинг: 0 / 0
05.11.2015, 10:13
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39095781
Казанский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Казанский
Гость
Eoltда идея норм, только вместо имени в таблице, надо хранить указатель на строку имени...То есть индекс массива строк.
Если диапазонов не более 65536, то таблица может быть массивом (0..100000) типа Integer, тогда он займет всего 200 кб.
Чтобы использовать весь диапазон чисел Integer, можно объявить массив строк с пределами (-32768 To 32767).
Вторая таблица - массив относительных расстояний, он скорее всего может быть даже типа Byte.

На всякий случай, в Excel эту задачу (поиск относительного расстояния от начала диапазона + название диапазона) можно решить с помощью функций ПОИСКПОЗ и ИНДЕКС.
...
Рейтинг: 0 / 0
05.11.2015, 18:17
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39095858
Eolt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Eolt
Участник
А для обратного преобразования, название диапазона и относительное смещение - в номер строки, какая будет структура данных?
...
Рейтинг: 0 / 0
05.11.2015, 19:45
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39095890
Казанский
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Казанский
Гость
Eolt,
для обратного преобразования - Collection или Scripting.Dictionary: ключ - название (оно по условию уникальное), значение - начало диапазона.
...
Рейтинг: 0 / 0
05.11.2015, 20:33
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39095959
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
EoltА для обратного преобразования, название диапазона и относительное смещение - в номер строки, какая будет структура данных?
Такая же. Но с сортировкой по имени диапазона.
...
Рейтинг: 0 / 0
05.11.2015, 22:08
| Ответить | Цитировать | Написать  
Быстрое получение ID диапазона в которое входит число
    #39095982
Bidgo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bidgo
Гость
Eolt какая будет структура данных?
Eolt, если эти диапазоны и их имена хранятся не в памяти, а в базе данных, тогда получение данных будет 1 селектом.
Название диапазона по точке: "select name from tabl where " & point & ">=n and " & point & "<=k"
Точка по названию и смещению: "(select n from tabl where name=" & diapazon & ") + " & sdvig
Примерно так.
...
Рейтинг: 0 / 0
05.11.2015, 23:11
| Ответить | Цитировать | Написать  
15 сообщений из 15, страница 1 из 1
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Быстрое получение ID диапазона в которое входит число
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=60&msg=39095982&tid=2155737]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 32ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 13ms
total:  138ms
созд. / загр.: 138ms
x
x
Закрыть


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