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

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
Space
Combo-маньяк
Combo-маньяк
 
Сообщения: 818
Зарегистрирован: 11.01.2007 (Чт) 1:19
Откуда: Украина

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

Сообщение Space » 18.09.2008 (Чт) 14:03

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

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

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

Сообщение Antonariy » 18.09.2008 (Чт) 14:26

Ничего не понятно. Однако попахивает извращением.
Лучший способ понять что-то самому — объяснить это другому.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14111
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 18.09.2008 (Чт) 14:32

Сортируй и используй бинарный поиск.
Lasciate ogni speranza, voi ch'entrate.

ANDLL
Великий гастроном
Великий гастроном
Аватара пользователя
 
Сообщения: 3450
Зарегистрирован: 29.06.2003 (Вс) 18:55

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

Сообщение ANDLL » 18.09.2008 (Чт) 15:25

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

Space
Combo-маньяк
Combo-маньяк
 
Сообщения: 818
Зарегистрирован: 11.01.2007 (Чт) 1:19
Откуда: Украина

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

Сообщение Space » 18.09.2008 (Чт) 16:51

ANDLL, спасибо. Меняется массив или не меняется, самым быстрым вариантом мне видется построение двоичного дерева по ID, в листья которого будут ложиться Idx. Чем больше будет массив ID, тем больший выигрыш будет давать двоичное дерево в скорости.

ANDLL
Великий гастроном
Великий гастроном
Аватара пользователя
 
Сообщения: 3450
Зарегистрирован: 29.06.2003 (Вс) 18:55

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

Сообщение ANDLL » 18.09.2008 (Чт) 17:01

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

Space
Combo-маньяк
Combo-маньяк
 
Сообщения: 818
Зарегистрирован: 11.01.2007 (Чт) 1:19
Откуда: Украина

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

Сообщение Space » 18.09.2008 (Чт) 17:57

ты имеешь ввиду поиск половинным методом или как там его? А время на сортировку при добавлении новых элементов? Хотя да, у меня добавление новых не так часто, как работа с массивом. А чё ты постоянно цитируешь весь мой текст?

Viper
Артефакт VBStreets
Артефакт VBStreets
Аватара пользователя
 
Сообщения: 4390
Зарегистрирован: 12.04.2005 (Вт) 17:50
Откуда: Н.Новгород

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

Сообщение Viper » 19.09.2008 (Пт) 7:39

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

Zenitchik
Постоялец
Постоялец
 
Сообщения: 369
Зарегистрирован: 21.12.2006 (Чт) 14:48

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

Сообщение Zenitchik » 03.10.2008 (Пт) 12:47

Кстати, при какой длине массива появляется преимущество интерполяционного поиска перед бинарным?
Знание английского языка - затрудняет понимание кода

alibek
Большой Человек
Большой Человек
 
Сообщения: 14111
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 03.10.2008 (Пт) 13:46

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

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

Денис
Доктор VB наук
Доктор VB наук
Аватара пользователя
 
Сообщения: 2734
Зарегистрирован: 07.11.2006 (Вт) 13:55
Откуда: Ейск, Краснодарский край

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

:?:
Программирование — богоизбранная дисциплина! Если бог и есть, то вселенную он скомпилировал, не иначе.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14111
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

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

Сообщение alibek » 03.10.2008 (Пт) 15:03

Потому что нужен быстрый поиск.
Lasciate ogni speranza, voi ch'entrate.

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

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

Сообщение tyomitch » 03.10.2008 (Пт) 15:30

А коллекция -- недостаточно быстро?
Изображение


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

    TopList