Поиск по массиву половинным делением и добавление элементов?

← →
Астро (2008-11-23 10:20) [0]

Такая задача. Ищем в упорядоченном массиве элемент половинным делением, и если его там нет - добавляем. Проблема в том, что если массив большой, то на каждый сдвиг его элементов уходит много времени.

Как такое можно организовать, чтобы работало побыстрее?

← →
palva © (2008-11-23 10:30) [1]

Использовать функцию move, а не поэлементный сдвиг.

← →
Астеро (2008-11-23 10:33) [2]

> palva © (23.11.08 10:30) [1]
>
> Использовать функцию move, а не поэлементный сдвиг.

Вопрос как принципиально сделать по-другому, чтобы работало быстрее?
Чтобы не надо было передвигать постоянно десятки мегабайтов.

← →
TUser © (2008-11-23 10:33) [3]

Использовать дерево, а не массив. Хотя бы простейшее бинарное, а если очень хочется, то красно-черное.

← →
Астро (2008-11-23 10:35) [4]

> TUser © (23.11.08 10:33) [3]
>
> Использовать дерево, а не массив. Хотя бы простейшее бинарное,
> а если очень хочется, то красно-черное.

Можно поподробнее?

← →
Астро (2008-11-23 10:38) [5]

> TUser © (23.11.08 10:33) [3]
>
> Использовать дерево, а не массив. Хотя бы простейшее бинарное

Как в бинарном дереве организовать поиск половинным делением?

← →
TUser © (2008-11-23 10:58) [6]

Оно самой судьбой предназначено для поиска за время log(n). Не хуже твоего поиска в массиве. Только места чуть больше займет. Прочитай про деревья у Кормена или Ахо или в лююбой другой книжке по алгоритмам.

зы. Извини, мне сегодня некогда подробно описывать, это и правда можно найти в любом мануале.

← →
palva © (2008-11-23 11:40) [7]

Вот здесь можно почитать
http://program.rin.ru/razdel/html/817.html

← →
sniknik © (2008-11-23 13:04) [8]

чтобы не парится можно использовать для данных вместо массива/самопального дерева рекордсет(ADORecordSet), десяток мегабайт для него несерьезны, сортировка(локальный индекс) "внутрях" тоже возможно используют деревья, но самому их строить не придется. поиск не входящего/вставка делаются моментально (замедление только изза кривого кода, либо действительно очень больших объемом).
вот с "половинным делением" туго, вряд ли локейт использует его, но с другой стороны, переделал на дерево тоже не сможешь использовать именно его, если в этом цель (учебный процесс?).
минус, придется переучиваться/переделывать, стиль работы отличается от работы с массивом.

← →
sniknik © (2008-11-23 13:07) [9]

и кстати если предубеждение против рекордсета, то простой стринглист с включенной сортировкой и игнорированием дубликатов при вставке.
правда, имхо, будет помедленнее.

← →
Petr V. Abramov © (2008-11-23 21:03) [10]

> то простой стринглист с включенной сортировкой и игнорированием
> дубликатов при вставке.

или что-то содранное с его реализации, с удалением ненужного и добавлением своего функционала
:)

← →
Астро (2008-11-24 02:30) [11]

> TUser © (23.11.08 10:58) [6]
>
> Оно самой судьбой предназначено для поиска за время log(n).
> Не хуже твоего поиска в массиве. Только места чуть больше
> займет. Прочитай про деревья у Кормена или Ахо или в лююбой
> другой книжке по алгоритмам.

Какое точное название книг?

> palva © (23.11.08 11:40) [7]
>
> Вот здесь можно почитать
> http://program.rin.ru/razdel/html/817.html

Какая-то он-лайн игра...

И вот что деревья то?
Допустим два элемента в начале 1 и 2. Корень дерева будет - 1. Потом добавили ещё миллион элементов от 3 до миллиона. Получается, дерево с одной веткой, то есть, тоже самое, что и массив, но чтобы найти миллионный элемент, надо перебрать миллион элементов. Это не подходит.

← →
MBo © (2008-11-24 05:22) [12]

>Получается, дерево с одной веткой
Если читать книжки, то там про это написано.
Чтобы не получилось, используют сбалансированные деревья.
Про красно-черное (Red-Black tree) уже сказали, еще можно отметить AVL-деревья, Treaps(дерамиды, декартовы деревья), на худой конец SkipLists (списки с пропусками)

← →
Астро (2008-11-24 06:00) [13]

> MBo © (24.11.08 05:22) [12]
>
> >Получается, дерево с одной веткой
> Если читать книжки, то там про это написано.
> Чтобы не получилось, используют сбалансированные деревья.
>
> Про красно-черное (Red-Black tree) уже сказали, еще можно
> отметить AVL-деревья, Treaps(дерамиды, декартовы деревья),
> на худой конец SkipLists (списки с пропусками)

Скажите, вы сами читали эти книжки?
Ощущение, что вы просто бросаетесь словами, по принципу авось угадаю с каким-нибудь из этих слов.

Если же вы действительно понимаете о чём пишите, то опишите конкретный подход, который по вашему мнению лучше всего сюда подходит - словами.

← →
TUser © (2008-11-24 07:58) [14]

Под описание задачи все эти подходы подходят. Про SkipLists я ничего не знаю.

← →
MBo © (2008-11-24 08:11) [15]

>Про SkipLists я ничего не знаю
Списки с пропусками, есть, например, в Бакнелле.
Обеспечивают примерно такое же асимптотическое время, как и сбал. деревья.

← →
Сергей М. © (2008-11-24 08:28) [16]

> Астро (23.11.08 10:20)

> если массив большой, то на каждый сдвиг его элементов уходит
> много времени

Показывай код "сдвига" ..

← →
palva © (2008-11-24 20:31) [17]

> Какое точное название книг?

Ахо-Ульмана по данной теме я вам читать не советую.
Балансировка деревьев хорошо описана здесь.
Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М. Мир,
1985
или здесь:
Рейнгольд Э., Нивергельт Ю., Део Н.
Комбинаторные алгоритмы. Теория и практика.
М.: Мир, 1980.
Там есть такие пункты:
6.4. Логарифмический поиск в динамических таблицах
6.4.2. Бинарные деревья сбалансированные по высоте.

> надо перебрать миллион элементов. Это не подходит.

Зря вы так. Поверьте, нам лучше знать, что вам подходит, а что нет. Человеку который задает такие вопросы:
> Как в бинарном дереве организовать поиск половинным делением?
обязательно нужно сначала узнать, что такое древовидные структуры данных, а уже потом заниматься динамической балансировкой.

← →
Астро (2008-11-25 05:31) [18]

> palva © (24.11.08 20:31) [17]
> Зря вы так. Поверьте, нам лучше знать, что вам подходит,
> а что нет. Человеку который задает такие вопросы:
> > Как в бинарном дереве организовать поиск половинным делением?
>
> обязательно нужно сначала узнать, что такое древовидные
> структуры данных, а уже потом заниматься динамической балансировкой.

А вам наверное стоит перечитать название темы, так как половинное деление в нём указано.

И не надо делать вид, что никто не знает, что такое древовидные структуры.
http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

Массив из за деревьев сразу разрастается так как добавляется left, right. А половинное деление становится невозможным.

← →
TUser © (2008-11-25 07:30) [19]

А тебе надо "найти элемент побыстрому" или "половинным делением"?

← →
TUser © (2008-11-25 07:32) [20]

Кстати, в насоветованной тебе литературе есть все, что приведено по твоей ссылке в википедии, и даже несколько больше. :)

← →
Труп Васи Доброго © (2008-11-25 08:53) [21]

Человек, чего ты тут людям мозг закакиваешь? Что значит "массив большой" и какой нафиг сдвиг???
Ты можешь сказать массив чего????
Если это массив интеджеров, то дарю бесплатную идею:
добавляй элемент в конец массива, а потом выполняй сортировку методом Quick Sort (см. в демосах Delphi)
Сортировка массива из 10000000 интеджеров этим методом на занюханом Целероне 2.8 занимает всего одну секунду. Куда тебе ещё быстрее???

← →
MBo © (2008-11-25 09:03) [22]

>добавляй элемент в конец массива, а потом выполняй сортировку методом Quick Sort

Это плохая идея.

Впрочем, автору, видимо, пофиг - непохоже, что он над советами задумывается.

← →
Palladin © (2008-11-25 09:10) [23]

Автор нагло разводит на код, вот и все.

← →
Rouse_ © (2008-11-25 09:11) [24]

Используй обычный массив и TList в качестве индексатора упорядоченных элементов. Если элемента нет - добавляешь в его конец массива, а индекс на него вставляешь в нужное место TList-а

← →
inoremap (2008-11-25 09:12) [25]

http://sourceforge.net/projects/decal/ спасает

← →
Труп Васи Доброго © (2008-11-25 09:20) [26]

> Это плохая идея.

Почему это плохая? За такие слова можно и обоснуем назвать! Или ты знаешь про поставленную задачу больше, чем тут указано?
Это нормальный метод работы баз нданных. Там данные хранятся без всякого упорядочивания.
Имеетря в виду, что сортировка производится перед тем как применять метод дихотомии, ведь ему надо именно этот метод применять.

← →
Palladin © (2008-11-25 09:24) [27]

> Почему это плохая?

потому что правильно построенный бинарный поиск по отсортированным элементам в случае ненахождения должен вернуть индекс по которому должен был бы располагаться не найденный элемент, куда он потом и вставляется.

← →
Труп Васи Доброго © (2008-11-25 09:29) [28]

> Ищем в упорядоченном массиве элемент половинным делением,
> и если его там нет - добавляем.

Где ты тут нашёл хоть слово про то, что новый элемент должен быть добавлен в определённое место, между меньшим и большим???? Сказано просто "добавлен" и всё.
А вот в БД при НЕнахождении возвращается не индекс, а NULL, и мне это больше нравится!

> правильно построенный бинарный поиск по отсортированным
> элементам в случае ненахождения должен вернуть индекс по
> которому должен был бы располагаться не найденный элемент,
> куда он потом и вставляется

Это где сказано??? В твоём случае индекс зависит от реализации, а это неправильно, ибо неоднозначно. А вот NULL, даёт однозначный ответ в любом случае.

> Труп Васи Доброго © (25.11.08 09:29) [28]

по смыслу выходит...

Ищем в "порядоченном массиве" потом добавляем. Хотя, конечно, прямо не указано, что массив должен остаться упорядоченным. Но косвенно об этом говорит фраза "каждый сдвиг его элементов". Значит автор все таки вставляет в нужную позицию. Вся проблема его в том что "на каждый сдвиг его элементов уходит много времени". Начали предлагать товарищу другие структуры данных для решения задачи быстрой вставки. Читать автор все вышеприведенные материалы не утрудняется, готовое решение требует, что бы за него подумали, что же лучше. Причем, какие критерии ему нужны, наибыстрый поиск, наибыстрая вставка или наименьший расход памяти - остается загадкой.

> Сортировка массива из 10000000 интеджеров этим методом на
> занюханом Целероне 2.8 занимает всего одну секунду. Куда
> тебе ещё быстрее???

Нифига себе быстро ... а если мне надо это делать миллион раз ... я скорее сам трупом стану.

Впрочем, автор, похоже, действительно не в курсе, чего ему надо. Может и не задачу решить, а преподу принести "половинное деление", а оно у него с косяками выходит.

>Почему это плохая?
Например, потому что QuickSort будет работать в данном случае намного медленнее сортировки вставками и даже пузырьком. А сортировка вставками с бинарным поиском еще побыстрее - по сути это и получается нахождение места и сдвиг части массива. Структуры данных, о которых уже упоминали, ускорят это дело радикально.

>Это нормальный метод работы баз нданных. Там данные хранятся без всякого упорядочивания
Базы данных часто используют Б-деревья (деревья с сильным ветвлением).

> Ищем в "порядоченном массиве" потом добавляем. Хотя, конечно,
> прямо не указано, что массив должен остаться упорядоченным.
> Но косвенно об этом говорит фраза "каждый сдвиг его элементов".

Я не пойму, ты программист или философ?
Я вижу чётко поставленную задачу по поиску значения в массиве определённым методом: "Ищем в упорядоченном массиве элемент половинным делением"
Для того, чтобы дихотомия работала массив должен быть упорядоченным, это факт.
Результат поиска должен быть логическим (нашли/не нашли): "и если его там нет" (заметь не сказано о результате в виде индекса, как ты предполагаешь, есть чёткое указание что результат булевый)
Элемент должен быть добавлен в массив: " - добавляем." Опять же заметь - "добавляем", а не "вставляем", то есть дано указание чтобы элемент просто оказался в массиве, но ни слова о вставке в определённое место.
Всё осталное это не условие задачи, а неправильные рассуждения автора о избыточной раелизации вышеуказанной задачи.
Моё решение полностью решает поставленную задачу.

> причем здесь БД?

а при чём тут

> бинарный поиск

это твоё представление о задаче, а я смотрю в сторону БД, где данные не имеют никакого упорядочения, а упорядочиваются непосредственно перед выборкой по определённым условиям (при использовании определённого метода, в данном случае - дихотомии). Я считаю что простое упорядочивание элементов просто так, "чтобы былО" лишней тратой времени и ресурсов.

> а если мне надо это делать миллион раз

Где в задаче сказано о многокрантом повторении действий???
Не надо отсебятины! Будьте программистами, а те телепатами.

> Где в задаче сказано о многокрантом повторении действий???

Автора явно беспокоит медленное выполнение вставки. Это может быть связано с многократностью такого действия.

> inoremap (25.11.08 09:12) [25]
>
> http://sourceforge.net/projects/decal/ спасает

Здравая мысль.
Документация на русском здесь:
http://www.delphikingdom.com/asp/viewitem.asp?catalogid=891
http://www.delphikingdom.com/article/sdl.chm

> Автора явно беспокоит медленное выполнение вставки. Это
> может быть связано с многократностью такого действия.

Давай не будем гадать.
Никаких разъяснений он не дал, а понятия "массив большой" и "уходит много времени." чисто субъективные. Да и вопрос "Как такое можно организовать, чтобы работало побыстрее?" абсолютно австрактен. Насколько побыстрее? Может он на пентиум-1 это делает и ему надо комп сменить.
Или массив террабайтный, тогда любой способ будет "медленным". Без уточнения задачи и условий "улучшения" дальнейшее обсуждение не имеет смысла.

> Например, потому что QuickSort будет работать в данном случае
> намного медленнее сортировки вставками и даже пузырьком.
> А сортировка вставками с бинарным поиском еще побыстрее
> - по сути это и получается нахождение места и сдвиг части
> массива. Структуры данных, о которых уже упоминали, ускорят
> это дело радикально.

Это тоже голословное заявление. С таким же успехом можно посоветовать засунуть этот массив в БД и сделать Select с Insert и не морочить всем голову.

← →
Астро (2008-11-30 03:47) [38]

> Труп Васи Доброго © (25.11.08 08:53) [21]
> добавляй элемент в конец массива, а потом выполняй сортировку
> методом Quick Sort (см. в демосах Delphi)

Он гораздо тормознее сдвига.

> Rouse_ © (25.11.08 09:11) [24]
>
> Используй обычный массив и TList в качестве индексатора
> упорядоченных элементов. Если элемента нет - добавляешь
> в его конец массива, а индекс на него вставляешь в нужное
> место TList-а

При вставке в TList тоже надо всё сдвигать.

> Труп Васи Доброго © (25.11.08 09:29) [28]
>
> > Ищем в упорядоченном массиве элемент половинным делением,
>
> > и если его там нет - добавляем.
>
> Где ты тут нашёл хоть слово про то, что новый элемент должен
> быть добавлен в определённое место, между меньшим и большим?
> ??? Сказано просто "добавлен" и всё.

Если в упорядоченный массив добавлять элементы куда попало, то он после первого же добавления перестанет быть упорядоченным.

> Palladin © (25.11.08 09:42) [30]
>
>
> > Труп Васи Доброго © (25.11.08 09:29) [28]
>
> по смыслу выходит...
>
> Начали предлагать товарищу другие структуры данных
> для решения задачи быстрой вставки. Читать автор все вышеприведенные
> материалы не утрудняется, готовое решение требует, что бы
> за него подумали, что же лучше.

Тому, кто это уже делал ничего придумывать не надо, надо всего лишь объяснить. Если бы я знал ответ, то просто бы объяснил как сделать и всё, а не говорил, что мол прочитай все книги мира, может что-нибудь найдёшь.

← →
Астро (2008-11-30 04:03) [39]

По поводу этой задачи у меня есть идея использовать два массива. Большой и малый, кэш-массив. Малый при этом может располагаться просто в хвосте большого массива.

Все новые элементы добавляются в малый массив, а когда он заполниться, нужно пройтись по большому и расставить элементы малого в него.

Половинное деление в этом случае нужно выполнять по двум массивам сразу. Но из-за того, что малый массив невелик, время не должно сильно увеличиться.

Такой подход практически не увеличивал бы потребности в памяти.

Насчёт общего выигрыша в скорости - думаю должен быть, если основной массив большой.

Как вам идея?

>
> Насчёт общего выигрыша в скорости - думаю должен быть, если
> основной массив большой.
>

Зависит от задачи. Конкретно от того, насколько часто тебе надо добавлять элементы, и насколько часто искать новые.

Давай оценивать. Пусть поиск в массиве из N элементов выполняется за k1*logN, а вставка нового элемента - за k2*N. При размерах большого и малого массивов L и S соотвественно это будет занимать у тебя k1*(logS+logL) и k2*S + время на сортировку при объединении массивов. От последнего и бдет зависеть эффективность алгоритма.

Поиск по массиву половинным делением и добавление элементов? Найти похожие ветки