Динамические списки записей

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

Re: Динамические списки записей

Сообщение zub » 23.08.2020 18:30:41

>> как у него дела с доступом по индексу?
Так вы определитесь, что нужно, индекс или связный список. Конкретно эту реализацию я не смотрел, но если там и есть индекс, то костылем, т.к. это реализация двусвязного списка
zub
долгожитель
 
Сообщения: 2586
Зарегистрирован: 14.11.2005 23:51:26

Re: Динамические списки записей

Сообщение iskander » 23.08.2020 19:00:13

zub писал(а):Так вы определитесь...

Хм, именно я?
Дела обстоят как-то так:
Код: Выделить всё
                     индексация  вставка    удаление
  Массив             O(1)        O(N)       O(N)
  Двусвязный список  O(N)        O(1)       O(1)
  BST                O(Log(N))   O(Log(N))  O(Log(N))
iskander
постоялец
 
Сообщения: 306
Зарегистрирован: 08.01.2012 18:43:34

Re: Динамические списки записей

Сообщение zub » 23.08.2020 19:33:47

Извиняюсь, спутал с тсом. Пишу-читаю
с телефона. Отпуск :beer:
zub
долгожитель
 
Сообщения: 2586
Зарегистрирован: 14.11.2005 23:51:26

Re: Динамические списки записей

Сообщение Mirage » 24.08.2020 21:33:44

GAMER писал(а):Есть необходимость держать массив/списки/что-либо для записей. Полями записей являются строки, датавремя, указатели на MySQL-соединения.
В списке нужно добавлять и удалять записи, которые могут быть в середине, а не в конце списка.
Есть современные решения или делатть классически а-ля стеки, в которых елементом записи является указатель на следующий елемент?

или использовать динамический массив, в котором последний елемент пишеться на место удаляемого, а размер массива уменьшаеться на 1?


Все решения тут давно известны и "современных" нет. Разве что, соединения с БД хранятся в соотв. пуле и достаются по мере надобности. Но это тоже уже давно.
Связанные списки используются редко, т.к. обычно медленнее массивов.
Постановка непонятна - сохранять порядок нужно?
Если нет, то зачем вставлять элемент посередине? Проще и быстрее в конец добавить. Тогда точно лучше какую-нибудь коллекцию на основе массива взять.
А если да, то каким образом может подойти удаление с переносом последнего на место удаленного? Тогда надо понимать сравнительную частоту удалений/вставок по отношению к чтениям. Ну и характер чтений - полный проход или доступ по индексу.

Как с этим всем станет понятно, можно брать соотв. коллекцию из стандартного набора.
Mirage
энтузиаст
 
Сообщения: 879
Зарегистрирован: 06.05.2005 20:29:07
Откуда: Russia

Re: Динамические списки записей

Сообщение sts » 25.08.2020 00:32:48

Снег Север писал(а):Умные расставляют правильные приоритеты. Лично я за 30 лет вообще еще не встречал программ, для которых (если это не из приведенного мной выше перечня) скорость работы любого list'а была существенной.

а я постоянно, приходят и спрашивают можно чтото сделать - форма с динамической бизнес логикой от 40 секунд открывается - ну точно - тлист - переписываешь на самопальный (тутже накорябанный) связанный список - 400 млсек, спрашиваешь какого фига клиента мучаешь, они 5лет потратили на ожидание уже, а в ответ дебильная сентенция- ну я не подумал, оно же вроде быстро обычно, тьфу.

Добавлено спустя 2 минуты 57 секунд:
iskander писал(а):А как у него дела с доступом по индексу?


ирония в том там где тлист медленный, обычно обращение по индексу не нужно
sts
постоялец
 
Сообщения: 282
Зарегистрирован: 04.04.2008 12:15:44
Откуда: Тольятти

Re: Динамические списки записей

Сообщение GAMER » 25.08.2020 11:15:54

Есть программа, которая получает запросы и часто подключаеться к БД. Дабы не генерировать много новых подключений к БД, хочу сделать сессии, в которых будет время последней активности и время жизни. Вот эти сессии и хочу держать в списке. Количество сессий не должно быть большим, но поиск должен работать как по ИД сессии так и по времени.
Как оно построено, на базе мсассива или цепочки указателей - пока не важно, но удаление в середине - приветствуется (Кстати, при удалении в середине, все последующие индексы смещаются?).
Добавление будет в конце.
Аватара пользователя
GAMER
энтузиаст
 
Сообщения: 613
Зарегистрирован: 06.08.2008 13:41:07
Откуда: Ужгород-Днепр, Украина

Re: Динамические списки записей

Сообщение Снег Север » 25.08.2020 13:28:53

GAMER писал(а):Есть программа, которая получает запросы и часто подключаеться к БД

Не понимаю одного - зачем часто подключаться к БД? Почему не держать постоянно открытым одно соединение и переподключаться только при его потере?
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2626
Зарегистрирован: 27.11.2007 16:14:47

Re: Динамические списки записей

Сообщение MylnikovDm » 25.08.2020 14:20:59

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

Откуда вы взяли этот бред?
Откройте исходники и посмотрите. TFPList использует внутри массив PPointerList = ^TPointerList, который обычный статический массив TPointerList = array[0..MaxListSize - 1] of Pointer.
При добавлении и удалении элементов данный массив перераспределяется через ReallocMem.
TList внутри реализован точно также, поскольку внутри себя содержит поле FList: TFPList, в котором хранятся указатели на элементы списка. По сути TList есть обёртка над TFPList, которая добавляет интерфейс IFPObserved и набор функций для контроля за изменениями в списке.

Что касается вставки элементов, то отдельными элементами никто ничего не перемещает. Всё делается за одну операцию:
System.Move(Flist^[Index], Flist^[Index+1], (FCount - Index) * SizeOf(Pointer));

На большинстве процессоров это будет одна процессорная команда, которая перемещает в оперативной памяти набор байт с одного адреса в другой. А с учётом быстродействия современных процессоров вы будете замечать какие-либо ощутимые задержки только при размерах списков в десятки тысяч элементов и больше.
Опять же, что TFPList, что TList, при вставке элемента перемещают в памяти только указатели на элементы, а не сами элементы, так что с использованием на практике с ними никогда проблем не возникало. Не надо выдумывать.

Что касается связанных списков, то тут я полностью поддерживают Zub'a. Может быть вставка элемента и будет происходить "за фиксированное время", но вот доступ к элементу по его номеру (индексу) будет очень долгой. Причём тем больше, чем больше список и чем больший номер (индекс) элемента, к которому вы хотите получить доступ. В связи с чем возникает резонный вопрос, что вы делаете чаще, вставляете элементы внутрь списка или получаете к ним доступ по номеру (индексу)?
MylnikovDm
постоялец
 
Сообщения: 102
Зарегистрирован: 15.02.2007 21:26:10
Откуда: Челябинск

Re: Динамические списки записей

Сообщение zub » 25.08.2020 14:47:41

GAMER если планируются активные поиски то посмотрите в сторону tmap или tdictionary. Но т.к. количество планируется небольшим то думаю что брать за основу - монописуально. Разницы не увидеть. Я в случаях когда надо и массивно добавлять удалять и искать делаю хранение в массиве с пометкой удаленного элемента а не физическим его удалением + несколько поисковых индексов для быстрого нахождения по нужным ключам
zub
долгожитель
 
Сообщения: 2586
Зарегистрирован: 14.11.2005 23:51:26

Re: Динамические списки записей

Сообщение GAMER » 25.08.2020 16:42:13

Снег Север писал(а):Не понимаю одного - зачем часто подключаться к БД? Почему не держать постоянно открытым одно соединение и переподключаться только при его потере?

Могут буть паралельные подключения.

Добавлено спустя 2 минуты 11 секунд:
Пока пощупаю что и как, потом буду смотреть, что не устраивает.
Аватара пользователя
GAMER
энтузиаст
 
Сообщения: 613
Зарегистрирован: 06.08.2008 13:41:07
Откуда: Ужгород-Днепр, Украина

Re: Динамические списки записей

Сообщение Снег Север » 25.08.2020 21:19:51

GAMER писал(а):Могут буть паралельные подключения.

Если приложение многопоточное, тогда понятно. Но я бы вместо списков в программе сделал бы таблицу в БД для учета подключений.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2626
Зарегистрирован: 27.11.2007 16:14:47

Re: Динамические списки записей

Сообщение GAMER » 26.08.2020 10:05:02

Снег Север писал(а):Но я бы вместо списков в программе сделал бы таблицу в БД для учета подключений.


Такой вариант встречал, но его плюсы больше в том, когда кроме собственно подключений к БД, нужно хранить много другой информации. Ну и плюс, самих сессий много. У меня, пока не много (предполагаю). Практика покажет, какой метод покажет себя лучше.
Аватара пользователя
GAMER
энтузиаст
 
Сообщения: 613
Зарегистрирован: 06.08.2008 13:41:07
Откуда: Ужгород-Днепр, Украина

Re: Динамические списки записей

Сообщение Mirage » 27.08.2020 01:43:26

А, т.е. пул соединений с БД и делается. :)
Готового чтоли нет?
Mirage
энтузиаст
 
Сообщения: 879
Зарегистрирован: 06.05.2005 20:29:07
Откуда: Russia

Re: Динамические списки записей

Сообщение GAMER » 27.08.2020 10:43:47

А готовый это как?
Аватара пользователя
GAMER
энтузиаст
 
Сообщения: 613
Зарегистрирован: 06.08.2008 13:41:07
Откуда: Ужгород-Днепр, Украина

Re: Динамические списки записей

Сообщение Снег Север » 27.08.2020 11:01:09

GAMER писал(а):А готовый это как?

Как у MySQL сервера, например. Сервер сам следит за пулом соединений.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2626
Зарегистрирован: 27.11.2007 16:14:47

Пред.След.

Вернуться в Общее

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

Сейчас этот форум просматривают: Yandex [Bot] и гости: 5

Рейтинг@Mail.ru