Оценить сложность вставки строк в ДМУ списка?

Question

[ccc35]

Есть двусвязный список с динамическими массивами указателей на строки. При загрузке файла строки распределяются упорядочено в узлах. Каждый следующий узел в 2 раза больше предыдущего. Размер первого узла 10 строк. При одновременной загрузке файла от 1 до 1000 раз длиной 175 строк и весом 11кб порядок роста функции y=7725x^2.001. Вопрос. Нормально ли это и можно ли добиться порядка роста функции меньше квадратичной ?

Comments

[Иван Смирнов]

Честно говоря, я ничего не понял. Если вы просто проходитесь по файлу, и добавляете каждую строчку из него в новый элемент списка, то сложность алгоритма составляет O(n). Если таки нет, объясните лучше, что вы делаете.

[Mercury13]

Какой функции? Сложность должна быть не очень велика, и ты, вероятно, что-то упустил.

[ccc35]

Mercury13: Иван Смирнов:
Извиняюсь. Задача дана не полностью.
Опишу заново. Есть двусвязный список. Каждый элемент которого содержит ДМУ на строки. Первый список размером 10. Каждый следующий в 2 раза больше. В списки загружается файл из 175 строк. При его загрузке 1000 раз суммарное кол-во строк в списках будет 175 000. Загружаться строки должны упорядоченно. При каждой новой загрузке все предыдущие строки сортируются заново. В этом вся проблема.
Было проведено тестирование зависимости роста трудоёмкости от числа загрузок строк. Порядок роста зависимости на мой взгляд очень большой y=7725x^2.001. Вопрос в том, можно ли добиться этого порядка меньше квадратичного ?

[Mercury13]

Трудно что-то посоветовать, много не выиграешь.
1. Структура данных, дающая константный op[].
2. Сортировка, дающая выигрыш на почти отсортированных данных.

[Иван Смирнов]

Mercury13 Я опять так и не понял задачу (нет, может я дурак =): что такое дму, и как одна строка преобразовывается во много элементов? И почему вы храните всё это именно в списке? Какие запросы вам потом на этом списке надо выполнять? Судя по тому что написано сейчас, может быть вам действительно стоит посмотреть в сторону деревьев? Как вариант ещё в сторону map reduce посмотреть для формирования всего этого, но пока больше ничего не могу сказать.

[Mercury13]

Иван Смирнов: ДМУ = динамический массив указателей

Answer 1

[Schullz]

Нужно помещать строки в самобалансирующееся дерево (АВЛ, красно-чёрное и т.п.). В C++ реализовано в STL-контейнерах set и muliset. Сложность добавления будет - логарифм

Comments

[Mercury13]

Хороший вариант. Но надо бы спросить, какие нужны дополнительные вещи наподобие константного op[].

[Schullz]

Mercury13: а какая структура позволяет хранить элементы упорядоченно, чтобы ещё доступ был за константу, и добавление не хуже, чем за логарифм?