Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
04.11.2015, 18:11
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Есть отрезок случайной длинны, допустим от 0 до 100000 едениц. Он разбивается на N диапазонов, тоже случайного размера. Каждый диапазон имеет уникальное сгенерированное название типа "ASWDVGDEDS". Затем приходит случайное число от 0 до 100000, нужно вернуть название диапазона, в который входит эта точка и относительное расстояние от точки начала найденного диапазона. Как реализовать такую задачу, чтобы название диапазона и точка в нем возвращались максимально быстро? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
04.11.2015, 18:36
|
|||
|---|---|---|---|
|
|||
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Например, при разбивании отрезка генерировать 3-мерный массив - первая точка, последняя точка и название отрезка. Затем в цикле проверять массив на принадлежность полученной точки.. Если точка больше первого элемента массива (первой точки отрезка) и меньше второго элемента (последней точки отрезка), возвращать 3-й элемент (название) и разницу между имеющейся точкой и первым элементом массива (то есть относительное расстояние от начала отрезка). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
04.11.2015, 18:51
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Bidgo, тут проблема в том, что если будут тысячи диапазонов, надо делать тысячи проверок на принадлежность точки. А хотелось бы как-то сразу получать, с минимальными затратами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
04.11.2015, 18:53
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Это-ж хэш-таблица! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
04.11.2015, 18:54
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
hclubmkЭто-ж хэш-таблица! поясни ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
04.11.2015, 19:02
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Bidgo правильно подсказал, нужно построить индексированную таблицу, упорядочить ее по этим самым индексам, и искать бинарным поиском необходимый индекс/число ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 03:49
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Для бинарного поиска достаточно 2-мерного массива, где в 1-й размерности будут значение конца отрезка, а во 2-й - имя соответствующего отрезка. Для нулевого значения N всегда возвращать имя первого отрезка: If N = 0 Then N = 1 Бинарный поиск достаточно быстрый, но быстрее будет, если создать 1-мерный массив с элементами от 0 до 100000, в которые записать название отрезка, соответствующее каждому значению. Тогда для значения N достаточно заглянуть во N-й элемент массива. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 08:37
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
ZVI прекрасная идея ноEolt и относительное расстояние от точки начала найденного диапазона.поэтому массив двумерный, с индексом внутреннего смешения в диапазоне одинакового имени. №инд смещимя10имя121имя132имя140имя250имя361имя370имя481имя492имя4 правда, такая такая таблица должна иметь размерность, равную количеству возможных чисел, а не количеству имен, но судя из первой строки условия, для ТС это не критично. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 09:59
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
да идея норм, только вместо имени в таблице, надо хранить указатель на строку имени, чтобы уменьшить объем потребляемой памяти ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 10:13
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Eoltесли будут тысячи диапазонов, надо делать тысячи проверок на принадлежность точки. От 10 до 14 проверок. Если диапазоны хранить в виде массива (начало-конец-имя), сортированного по началу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 18:17
|
|||
|---|---|---|---|
|
|||
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Eoltда идея норм, только вместо имени в таблице, надо хранить указатель на строку имени...То есть индекс массива строк. Если диапазонов не более 65536, то таблица может быть массивом (0..100000) типа Integer, тогда он займет всего 200 кб. Чтобы использовать весь диапазон чисел Integer, можно объявить массив строк с пределами (-32768 To 32767). Вторая таблица - массив относительных расстояний, он скорее всего может быть даже типа Byte. На всякий случай, в Excel эту задачу (поиск относительного расстояния от начала диапазона + название диапазона) можно решить с помощью функций ПОИСКПОЗ и ИНДЕКС. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 19:45
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
А для обратного преобразования, название диапазона и относительное смещение - в номер строки, какая будет структура данных? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 20:33
|
|||
|---|---|---|---|
|
|||
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Eolt, для обратного преобразования - Collection или Scripting.Dictionary: ключ - название (оно по условию уникальное), значение - начало диапазона. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 22:08
|
|||
|---|---|---|---|
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
EoltА для обратного преобразования, название диапазона и относительное смещение - в номер строки, какая будет структура данных? Такая же. Но с сортировкой по имени диапазона. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2015, 23:11
|
|||
|---|---|---|---|
|
|||
Быстрое получение ID диапазона в которое входит число |
|||
|
#18+
Eolt какая будет структура данных? Eolt, если эти диапазоны и их имена хранятся не в памяти, а в базе данных, тогда получение данных будет 1 селектом. Название диапазона по точке: "select name from tabl where " & point & ">=n and " & point & "<=k" Точка по названию и смещению: "(select n from tabl where name=" & diapazon & ") + " & sdvig Примерно так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=60&mobile=1&tid=2155737]: |
0ms |
get settings: |
9ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
33ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
48ms |
get tp. blocked users: |
2ms |
| others: | 292ms |
| total: | 419ms |
| 0 / 0 |
