Страница 1 из 1

Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 14:03
Space
Есть массив Long чисел, неких ID. Можно ли их связать с массивом других чисел Long (Idx) не используя ни одного перебора по любым массивам (прямая связь)? Т.е. каждому произвольному числу ID соответствует 1 произвольное число Idx - в самом простейшем случае можно открыть массив Long Ubound=максимальное ID и присвоить его элементам соответствующие Idx, НО, такой массив сожрёт нереально много памяти, если ID произвольный. На практике же, ID не произволен, но довольно велик, а имеется весьма небольшой массив этих ID, скажем 1000 элементов, поэтому здесь можно попробовать обойтись без жертв памяти :)

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 14:26
Antonariy
Ничего не понятно. Однако попахивает извращением.

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 14:32
alibek
Сортируй и используй бинарный поиск.

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 15:25
ANDLL
Space писал(а):Есть массив Long чисел, неких ID. Можно ли их связать с массивом других чисел Long (Idx) не используя ни одного перебора по любым массивам (прямая связь)? Т.е. каждому произвольному числу ID соответствует 1 произвольное число Idx - в самом простейшем случае можно открыть массив Long Ubound=максимальное ID и присвоить его элементам соответствующие Idx, НО, такой массив сожрёт нереально много памяти, если ID произвольный. На практике же, ID не произволен, но довольно велик, а имеется весьма небольшой массив этих ID, скажем 1000 элементов, поэтому здесь можно попробовать обойтись без жертв памяти :)
Задача типичная, и способов решения, простых и сложных очень много.
Из простых:
Если массив не меняется то можно его просто сортировать и тогда поиск в нем будет со скоростью lg n.(как уже отметилось выше)
Если массив меняется, разбей его в двоичное дерево. Тут будет быстрым и поиск и вставка.
Но так или иначе, в общем случае добиться скорости большей чем lg n можно будет только созданием массива который "сожрёт нереально много памяти"

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 16:51
Space
ANDLL, спасибо. Меняется массив или не меняется, самым быстрым вариантом мне видется построение двоичного дерева по ID, в листья которого будут ложиться Idx. Чем больше будет массив ID, тем больший выигрыш будет давать двоичное дерево в скорости.

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 17:01
ANDLL
Space писал(а):ANDLL, спасибо. Меняется массив или не меняется, самым быстрым вариантом мне видется построение двоичного дерева по ID, в листья которого будут ложиться Idx. Чем больше будет массив ID, тем больший выигрыш будет давать двоичное дерево в скорости.
Операция поиска в сортированном массиве не уступает по скорости поиску в двоичном дереве, зато такой массив экономит память. А важно это, или нет - зависит от имеющейся ситуации.
Вобщем, дерево это не панацея

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 18.09.2008 (Чт) 17:57
Space
ты имеешь ввиду поиск половинным методом или как там его? А время на сортировку при добавлении новых элементов? Хотя да, у меня добавление новых не так часто, как работа с массивом. А чё ты постоянно цитируешь весь мой текст?

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 19.09.2008 (Пт) 7:39
Viper
Space писал(а):ты имеешь ввиду поиск половинным методом или как там его?
Это и есть бинарный поиск.
Space писал(а):А время на сортировку при добавлении новых элементов?
Если у тебя массив отсортитрован, то при добавлении элемента, его позиция определяется все тем же бинарным поиском, ничего сортировать еще раз не надо.
Space писал(а):Хотя да, у меня добавление новых не так часто, как работа с массивом.
Тем более.

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 03.10.2008 (Пт) 12:47
Zenitchik
Кстати, при какой длине массива появляется преимущество интерполяционного поиска перед бинарным?

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 03.10.2008 (Пт) 13:46
alibek
Zenitchik писал(а):Кстати, при какой длине массива появляется преимущество интерполяционного поиска перед бинарным?

При большой, в прикладных задачах таких ситуаций скорее всего никогда не возникнет. А если возникнут, то целесообразнее использовать СУБД.
Обычно бинарного поиска всегда достаточно; если объем данных большой, то никто не мешает "проиндексировать индекс" и вначале найти область поиска, а в ней уже искать запись.

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 03.10.2008 (Пт) 14:48
Денис
Я не понимаю, почему нельзя сделать структуру:
Код: Выделить всё
Private Type EXAMPLE
   ID As Long
   Idx As Long
End Type

И обьявить массив с таким типом.
Код: Выделить всё
Private Sub Form_Load()
   
   Dim A1(1000) As EXAMPLE
   
   With A1(66)
      .ID = 12
      .Idx = 13
   End With
   
   Debug.Print A1(66).ID, A1(66).Idx
   
End Sub

:?:

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 03.10.2008 (Пт) 15:03
alibek
Потому что нужен быстрый поиск.

Re: Прямые связи массивов, скажем так :)

СообщениеДобавлено: 03.10.2008 (Пт) 15:30
tyomitch
А коллекция -- недостаточно быстро?