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

[zub]

>> как у него дела с доступом по индексу?
Так вы определитесь, что нужно, индекс или связный список. Конкретно эту реализацию я не смотрел, но если там и есть индекс, то костылем, т.к. это реализация двусвязного списка

[iskander]

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

Хм, именно я?
Дела обстоят как-то так:

Код: Выделить всё

                     индексация  вставка    удаление
  Массив             O(1)        O(N)       O(N)
  Двусвязный список  O(N)        O(1)       O(1)
  BST                O(Log(N))   O(Log(N))  O(Log(N))


[zub]

Извиняюсь, спутал с тсом. Пишу-читаю
с телефона. Отпуск :beer:

[Mirage]

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

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

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

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

[sts]

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

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

Добавлено спустя 2 минуты 57 секунд:

А как у него дела с доступом по индексу?

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

[GAMER]

Есть программа, которая получает запросы и часто подключаеться к БД. Дабы не генерировать много новых подключений к БД, хочу сделать сессии, в которых будет время последней активности и время жизни. Вот эти сессии и хочу держать в списке. Количество сессий не должно быть большим, но поиск должен работать как по ИД сессии так и по времени.
Как оно построено, на базе мсассива или цепочки указателей - пока не важно, но удаление в середине - приветствуется (Кстати, при удалении в середине, все последующие индексы смещаются?).
Добавление будет в конце.

[Снег Север]

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

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

[MylnikovDm]

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. Может быть вставка элемента и будет происходить "за фиксированное время", но вот доступ к элементу по его номеру (индексу) будет очень долгой. Причём тем больше, чем больше список и чем больший номер (индекс) элемента, к которому вы хотите получить доступ. В связи с чем возникает резонный вопрос, что вы делаете чаще, вставляете элементы внутрь списка или получаете к ним доступ по номеру (индексу)?

[zub]

GAMER если планируются активные поиски то посмотрите в сторону tmap или tdictionary. Но т.к. количество планируется небольшим то думаю что брать за основу - монописуально. Разницы не увидеть. Я в случаях когда надо и массивно добавлять удалять и искать делаю хранение в массиве с пометкой удаленного элемента а не физическим его удалением + несколько поисковых индексов для быстрого нахождения по нужным ключам

[GAMER]

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

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

Добавлено спустя 2 минуты 11 секунд:
Пока пощупаю что и как, потом буду смотреть, что не устраивает.

[Снег Север]

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

Если приложение многопоточное, тогда понятно. Но я бы вместо списков в программе сделал бы таблицу в БД для учета подключений.

[GAMER]

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

Такой вариант встречал, но его плюсы больше в том, когда кроме собственно подключений к БД, нужно хранить много другой информации. Ну и плюс, самих сессий много. У меня, пока не много (предполагаю). Практика покажет, какой метод покажет себя лучше.

[Mirage]

А, т.е. пул соединений с БД и делается.
Готового чтоли нет?

[GAMER]

А готовый это как?

[Снег Север]

А готовый это как?

Как у MySQL сервера, например. Сервер сам следит за пулом соединений.