Список. Помогите оценить сложность.

[dr.Faust]

Я переодически посещаю проект вопросов от гугла. И как-то наткнулся там на это.
Вопрос вобщем-то звучал и раньше, да и сам я с этой проблемой сталкивался. Есть мнение, что в этих случаях надо использовать базу данных, но тем кто работал с реальными данными, а не с набором из сотни документов, громко названных данными, понятно, что это не выход.
Итак, проблема обозначена. Решение вроде бы очевидное - надо перебрать значения диапазона и отобрать уникальные. Но тут же упираемся в проблему поиска - как убедится, что значение уникальное? Сравнивать со всеми уже отобранными? Бред...
Для быстроты поиска данные придётся хранить упорядоченными. В Ocean Runtime Чегототам есть класс с помощью котоорого можно сортировать массивы, но сортировать массивы после каждого добавления тоже бред. Значит нужна структура позволяющая легко выполнить вставку. Очевидно это список.
Дёрнул меня чёрт накропать быстренько класс списка для Бэйсик. Посмотрел я на творение рук своих, ужаснулся, и решил делать в обычном массиве со сдвигом части данных при вставке. Не пошло... Ну не идёт и всё. Вернулся к идеи списка, решив переписать всё с 0. Начал и тут меня торкнуло - каждый раз перебирая элементы списка до нужного, мне придётся выполнять в среднем N/2 сравнений, а если бы у меня был массив, то сравнений было бы не так много (корень из N плюс одно?). Возник вопрос - а так ли сэкономит мне время список?

Итак, помогите оценить сложность задачи.

Используем массив. Сортировка вставкой.
1 Поиск элемента - корень из N плюс одно сравнение (включая считывание из массива)
2 Вставка элемента - N/2 записей в массив

Используем двусвязный список.
1 Поиск элемента - N/2 сравнений? Тут я вообще в ступоре. Так ли это если список двусвязный - я же могу практически постоянно помнить медиану множества и начинать проверку как с начала, так и с конца списка, если вновь поступивший элемент больше медианы?
2 Ну со вставкой всё понятно - 5 записей (сами данные + 4 ссылки)

На всякий случай прилагаю код вновь начатого класса.

Код Выделить Развернуть



Option Compatible
Option ClassModule

' массивы списка
Private aData() As Variant rem hide
Private aKeys() As Variant rem hide
Private aNext() As Long rem hide
Private aPrevius() As Long rem hide
Private aPool() As Long rem hide
Private aBusy() As Boolean rem hide
' переменные списка
Private bSafety As Boolean rem hide
Private iSize As Long rem hide
' массив кэша индексов


' aData(0) -
' aKeys(0) -
' aNext(0) - Первый элемент списка
' aPrevius(0) -
' aPool(0) - Индекс следующего индекса свободного элемента
' aBusy - Отметки о занятости
Private Sub Create (Optional ByVal iSizeIn As Long)
If IsMissing(iSizeIn) Then
iSize = UBound(aData)
Else
iSize = iSizeIn
End If
Dim i As Long
If iSize < 1 Then
bSafety = 1
iSize = 1024
End If
If iSize < 8 Then iSize = 1024

ReDim aData(iSize) ' данные
ReDim aKeys(iSize) ' ключи данных
ReDim aNext(iSize) ' ссылки на следующий элемент
ReDim aPrevius(iSize) ' ссылки на предыдущий элемент
ReDim aPool(iSize) ' пул свободных индексов
ReDim aBusy(iSize) ' кэш меток ииндексов
' заполняем пул
For i = 1 To iSize
aPool(i) = i
Next
' и устанавливаем указатель на его начало
aPool(0) = 1
End Sub

' ПОЛУЧЕНИЕ ДАННЫХ ______________________________________________________________________________________________________________________________________

Private Function countItems () As Long
' Вовращает количество элементов в Списке
countItems = aPool(0) - 1
End Function

Private Function isOrder () As Boolean
' проверяет упорядоченность списка и возвращает True, если список упорядочен
Dim iNumItem As Long ' - количество элементов в списке
Dim iIndex As Long
iNumItem = aPool(0) - 1
Dim i As Long
If iNumItem < 2 Then
isOrder = 1
End If
iIndex = aNext(0)
For i = 1 To iNumItem-1
If aKeys(iIndex) > aKeys(aNext(iIndex)) Then
isOrder = 0
Exit Function
End If
iIndex = aNext(iIndex)
Next
isOrder = 1
End Function

Private Function getList () As Variant
' Возвращает список в виде массива
Dim iNumItem As Long ' - количество элементов в списке
Dim iNIndex As Long
iNumItem = aPool(0) - 1
Dim aResult() As Variant
Dim i As Long
If iNumItem=0 Then
getList = aResult
Exit Function
End If
ReDim aResult(iNumItem-1)
iNIndex = aNext(0)
For i = 0 To iNumItem-1
aResult(i) = aData(iNIndex)
iNIndex = aNext(iNIndex)
Next
getList = aResult
End Function

' ДОБАВЛЕНИЕ В СПИСОК ___________________________________________________________________________________________________________________________________

Private Function PutToStart (ByVal iData As Variant, Optional ByVal iKey As Variant) As Long
' Помещаем элемент в начало списка
' -2 - ошибка
' -1 - переполнение
' +x - инедкс (ничего общего с номером в списке)
' ОБЩАЯ ЧАСТЬ НАЧАЛО =================================================================================================================================
' Проверим на переполнение
If aPool(0) > iSize Then
If bSafety Then
reCreate
Else
PutToStart = -1
Exit Function
End If
End If
' проверим ключ
If IsMissing (iKey) Then
If IsNumeric (iData) Or IsString(iData) Then
iKey = iData
Else
PutToStart = -2
Exit Function
End If
End If
' переменные
Dim iNumItem As Long ' - количество элементов в списке
Dim iIndex As Long ' - индекс добаляемого элемента
Dim iPIndex As Long ' - индекс предыдущего элемента
Dim iNIndex As Long ' - индекс следующего элемента
iNumItem = aPool(0) - 1
' ОБЩАЯ ЧАСТЬ КОНЕЦ =================================================================================================================================
' Получаем все индексы
' берём индекс из пула свободных адресов
iIndex = aPool(aPool(0))

If iNumItem = 0 Then ' и если нет ни одного пункта...
iNIndex = iIndex
iPIndex = iIndex
Else ' а если есть, то получаем индексы
' индекс следующего элемента (бывший первый)
iNIndex = aNext(0)
' индекс предыдущего элемента
iPIndex = aPrevius(iNIndex)
End If
' Устанавливаем текущий элемент как первый
aNext(0) = iIndex
' ОБЩАЯ ЧАСТЬ НАЧАЛО =================================================================================================================================
' помещаем данные иключи
aData(iIndex) = iData
aKeys(iIndex) = iKey
' устанавливаем ссылки
aNext(iIndex) = iNIndex ' на следующий элемент
aPrevius(iIndex) = iPIndex ' на предыдущий элемент
' изменяем ссылки
aNext(iPIndex) = iIndex ' у предыдущего ссылку на следующий
aPrevius(iNIndex) = iIndex ' у следующего ссылку на предыдущий
' помечаем элемент как занятый и сдвигаем указатель в пуле свободных адресов
aBusy(iIndex) = 1
aPool(0) = aPool(0)+1
PutToStart = iIndex
' ОБЩАЯ ЧАСТЬ КОНЕЦ =================================================================================================================================
End Function

Private Function PutToEnd (ByVal iData As Variant, Optional ByVal iKey As Variant) As Long
' Помещаем элемент в начало списка
' -1 - переполнение
' +x - инедкс (ничего общего с номером в списке)
' ОБЩАЯ ЧАСТЬ НАЧАЛО =================================================================================================================================
' Проверим на переполнение
If aPool(0) > iSize Then
If bSafety Then
reCreate
Else
PutToEnd = -1
Exit Function
End If
End If
' проверим ключ
If IsMissing (iKey) Then
If IsNumeric (iData) Or IsString(iData) Then
iKey = iData
Else
PutToEnd = -2
Exit Function
End If
End If
' переменные
Dim iNumItem As Long ' - количество элементов в списке
Dim iIndex As Long ' - индекс добаляемого элемента
Dim iPIndex As Long ' - индекс предыдущего элемента
Dim iNIndex As Long ' - индекс сдежующего элемента
iNumItem = aPool(0) - 1
' ОБЩАЯ ЧАСТЬ КОНЕЦ =================================================================================================================================
' Получаем все индексы
' берём индекс из пула свободных адресов
iIndex = aPool(aPool(0))
If iNumItem = 0 Then
iNIndex = iIndex
iPIndex = iIndex
Else
' индекс следующего элемента
iNIndex = aNext(0)
' индекс предыдущего элемента
iPIndex = aPrevius(iNIndex)
End If
' ОБЩАЯ ЧАСТЬ НАЧАЛО =================================================================================================================================
' помещаем данные
aData(iIndex) = iData
aKeys(iIndex) = iKey
' устанавливаем ссылки
aNext(iIndex) = iNIndex ' на следующий элемент
aPrevius(iIndex) = iPIndex ' на предыдущий элемент
' изменяем ссылки
aNext(iPIndex) = iIndex ' у предыдущего ссылку на следующий
aPrevius(iNIndex) = iIndex ' у следующего ссылку на предыдущий
' помечаем элемент как занятый и сдвигаем указатель в пуле свободных адресов
aBusy(iIndex) = 1
aPool(0) = aPool(0)+1
PutToEnd = iIndex
' ОБЩАЯ ЧАСТЬ КОНЕЦ =================================================================================================================================
End Function

' УДАЛЕНИЕ ИЗ СПИСКА ___________________________________________________________________________________________________________________________________

Private Function DelItems (ByVal iNumS As Long, ByVal iNumE As Long) As Long
' Удалить элементы от iNumS до iNumE включительно
' -1 - список пуст
' 0 - удаление за границами списка
' x - количество удалённых элементов
' - ОБЩАЯ ЧАСТЬ НАЧАЛО =================================================================================================================================
' Проверим на опусташение
If aPool(0) = 1 Then ' список пуст
DelItems = -1
Exit Function
End If

Dim iNumItem As Long ' - количество элементов в списке
Dim iIndexS As Long ' - индекс первого элемента
Dim iIndexE As Long ' - индекс второго элемента
Dim iPIndex As Long ' - индекс предыдущего элемента
Dim iNIndex As Long ' - индекс сдежующего элемента
iNumItem = aPool(0) - 1
' - ОБЩАЯ ЧАСТЬ КОНЕЦ =================================================================================================================================
' Удаление за границами списка
If iNumS > iNumItem Or iNumS < 1 Or iNumE > iNumItem Or iNumE < 1 Then
DelItems = 0
Exit Function
End If
' найдём первый элемент
Dim i1 As Long
Dim sfs As Long ' шагов от начала списка вперёд
Dim sfe As Long ' шагов от конца списка назад
Dim sfkif As Long ' шагов известного элемента вперёд
Dim sfkib As Long ' шагов известного элемента назад
' вычислим направление поиска
sfs = iNumS-1
sfe = iNumItem-iNumS
If sfs > sfe Then ' элемент ближе к концу списка
iIndexS = Previus(aNext(0)) ' индекс последнего элемента
For i1 = 1 To sfe
iIndexS = Previus(iIndexS)
Next
' iIndexS содержит индекс первого элемента удаляемой последовательности
Else ' элемент ближе к началу списка
iIndexS = aNext(0) ' индекс первого элемента
For i1 = 1 To sfs
iIndexS = aNext(iIndexS)
Next
' iIndexS содержит индекс первого элемента удаляемой последовательности
End If
' найдём последний элемент
sfs = iNumE-1
sfe = iNumItem-iNumE
sfkif = (iNumE - iNumS + iNumItem) mod iNumItem
sfkib = (iNumS - iNumE + iNumItem) mod iNumItem
If sfe < sfs and sfe < sfkif and sfe < sfkib Then ' элемент ближе к концу списка
iIndexS = Previus(aNext(0)) ' индекс последнего элемента
For i1 = 1 To iNumItem-iNumS
iIndexS = Previus(iIndexS)
Next
' iIndexS содержит индекс первого элемента удаляемой последовательности
ElseIf sfkif < sfs and sfkif < sfkib Then ' от известного вперёд
ElseIf sfkib < sfs Then ' от известного назад
Else ' элемент ближе к началу списка
iIndexS = aNext(0) ' индекс первого элемента
For i1 = 1 To iNumS-1
iIndexS = aNext(iIndexS)
Next
' iIndexS содержит индекс первого элемента удаляемой последовательности
End If















' - ОБЩАЯ ЧАСТЬ НАЧАЛО =================================================================================================================================
' изменяем ссылки
If aData(0) = iIndex Then ' если удаляется 1 элемент
If iNumItem = 1 Then ' если он к тому же последний...
aData(0) = 0
' помечаем элемент как свободный и возвращаем индекс в пул свободных адресов
aBusy(iIndex) = 0
aPool(0) = 1
aPool(1) = iIndex
DelItems = iIndex
Exit Function
Else
aData(0) = iNIndex
End If
End If
aNext(iPIndex) = iNIndex ' у предыдущего ссылку на следующий
aPrevius(iNIndex) = iPIndex ' у следующего ссылку на предыдущий
' помечаем элемент как свободный и возвращаем индекс в пул свободных адресов
aBusy(iIndex) = 0
aPool(0) = aPool(0)-1
aPool(aPool(0)) = iIndex
DelItems = iIndex
' - ОБЩАЯ ЧАСТЬ КОНЕЦ =================================================================================================================================
End Function


Функция DelItems пока не работоспособна.
Некоторые пояснения на словах:
aData -массив содержащий сами данные. aKeys - В этой реализации добавил массив ключей - а вдруг в качестве данных будут объекты? Например документы? Как их сравнивать? По ключам. Если ключ не передавать, а данные числа или строки, то сюда они будут тупо дублироваться. aNext - ссылки на следующий элемент (значение индекса данных во всех массивах), aNext(0) - ссылка на первый элемент (в остальных массивах кроме aPool этот индекс не используется - оставлен под всякого рода прикольные идеи оптимизации). aPrevius - ссылки на следующий элемент. aPool - Пул ещё не занятых или возвращённых в пул индексов (aPool(0) - ссылка на индекс начала пула). aBusy - Отметка о том, что инедекс используется (не помню для чего это придумывалось, но кажется что-то стоящее).

[VlhOwn]

Навскидку (устал, продумывать - не хватит пороху).

Анализируем возможные значения и строим целочисленную хэш-функцию.
Перебираем последовательно значения и строим новую последовательность по принципу: если хэш-функция от значения равна n, то в новой последовательности n-ный член устанавливаем в 1, иначе в 0. Если для очередного значения соответствующий член новой последовательности уже равен 1, то такое значение уже было.

[dr.Faust]

Я знаю этот метод - коллизий боюсь.

[prof-alex]

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

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

Тут получается +1 к тому issue где просили SQL встроить в Calc.

[VlhOwn]

Оценка сложности.

Предварительные замечания:
1. непонятно, почему сортировка вставкой - в данном случае наиболее неэффективный метод. Есть, например, сортировка пирамидой (сортировка с помощью двоичной кучи) со сложностью Nlog₂N
2. неясно, откуда ты взял свои оценки: поиск в упорядоченном массиве - log₂N, а не корень из N, поиск в упорядоченном двусвязном списке с медианой - N/2, а в односвязном - N; вставка элемента в упорядоченный массив  - в худшем случае N присваиваний
3. неясно также, что ты в дальнейшем будешь делать с полученной структурой - если она одноразовая, то список может и сгодится, но если с ней надо работать, массив имеет неоспоримое преимущество - прямой доступ по номеру.

Вот написал это все и понял, что не мудрствуй ты лукаво, реализуй сортировку пирамидой - и будет тебе счастье: что для сортировки вставкой, что для списка оценки получаются не лучше O(N²), а для сортировки пирамидой - O(Nlog₂N).

[dr.Faust]

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

Объясню. Есть сложные таблицы, по которым строятся весьма непростые (по обработке), функции. Это надо например при анализе рядов данных, например финансовых или погодных. Делать это в базе мягко говоря очень трудно.
Вместе с тем, там частой задачей является апроксимация  отдельных специяально отобранных точек прямыми. Причём линейную регрессию для всего ряда применить не выйдет, так как апроксимировать надо только специально отобранные точки. И вот выборка этих точек в отдельный массив помогла бы.
Тут бы и пригодилась функци Calc SQL. Но не база.

1. непонятно, почему сортировка вставкой - в данном случае наиболее неэффективный метод. Есть, например, сортировка пирамидой (сортировка с помощью двоичной кучи) со сложностью Nlog2N

Да речь уже и не идёт об этом. (Хотя я не помню в чём смысл сортировки пирамидой - Кнут сейчас потпирает тумбочку в кабинете, который замурован на время ремонта комнаты. prof-alex помог мне подцепить комп в кабинете и его диски по ssh, за что ему огромное спасибо. файло с дисков я повытаскивал. Но вытащить Кнута из под тумбочки по ssh не могу - fuse её не монтирует... )
Вопрос стал такой - Какова сложность поиска в двусвязном списке, медиана которого мне известна.

неясно, откуда ты взял свои оценки

Я говорю о "в среднем", а ты приводишь худший случай. Хотя, таки - да с корнем из N я изрядно протупил.
Однако...

вставка элемента в упорядоченный массив  - в худшем случае N присваиваний

... это точно не так!
Пусть у меня есть K элементов которые надо перебросить вставкой в массив.
Я создам массив размером 2K+1 и  первый элемент помещу в K+1. Следующий элемент я, в зависимости от его значения добавлю либо перед K+1, либо после. В дальнейшем добавляя элементы в массив мне достаточно будет сдвигать не более половины его элементов влево или вправо, в зависимости от того в какую половину его я вставляю элемент. Нужно только будет помнить левую и правую границу данных уже сидящих в массиве. При этом я могу быть абсолютно уверен, что у меня не будет переполнения или выхода границ данных за границы массива.
Так что в худшем случае K/2 присвоений!

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

Да просто упражнение в структоростроительстве Ну а придумывалось, для отбора уникальных элементов (тогда я не помнил, что есть способ проще - типа того, что ты предложил - с хэшами и двумерным массивом KxN, где N - число исходных элементов, а K - множество значений принимаемых хэш функцией - в худшем случае N/K сравнений.)

[dr.Faust]

По поводу Список vs Массив - а удалить блок данных из массива?
Задолбёшься оставшиеся перебрасывать. А из списка - изменить 2 или 3 (если удаляется и первый элемент) ссылки.

[VlhOwn]

Пирамида - двоичное дерево со следующими свойствами:
- ключ вершины больше ключа любого ее потомка
- длины путей от корня до любого листа различаются не более, чем на единицу

Двоичная куча - это реализация пирамиды массивом, обладающим следующими свойствами:
- вершина, представленная i-тым элементом массива, имеет левого сына с номером 2i и правого сына с номером 2i+1
- ключ левого сына вершины больше или равен ключу правого ее сына.

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

В твоем, Саша, случае использование двоичной кучи особенно целесообразно, поскольку ты добавляешь элементы в массив последовательно один за другим, и на каждом шаге у тебя сохраняется целостность двоичной кучи. Добавление элемента требует максимум loq₂N сравнений/перестановок и одной ячейки дополнительной памяти.

[JohnSUN]

Коллеги, а помните как Привалов с Кристобалем Хозевичем искали решение проблемы Бен Бецалеля?

Просто не удержался от хохмы, уж простите...

[вложение удалено Администратором]

[VlhOwn]

"Кадавр оторвался от чана и оглядел присутствующих. Нехороший это был взгляд, оценивающий какой-то..."

[dr.Faust]

Коллеги, а помните как Привалов с Кристобалем Хозевичем искали решение проблемы Бен Бецалеля?

JohnSUN, а я знал это ваше решение.
Не смотрел, но о существовании знал.
Но:
1 То что я описал выше, я делал когда ещё не знал.
2 Вопрос был Какова сложность поиска в двусвязном списке, если известна медиана, и можно выбирать направление поиска? Сейчас до меня уже дошло, что это O/2, где О - сложность поиска в двусвязном списке, та как список N с известной медианой можно представить в виде двух одинаковых списков N/2. А если известно среднее значение элементов списка?

[dr.Faust]

Двоичная куча - это реализация пирамиды массивом, обладающим следующими свойствами:- вершина, представленная i-тым элементом массива, имеет левого сына с номером 2i и правого сына с номером 2i+1- ключ левого сына вершины больше или равен ключу правого ее сына.

Спасибо.

[prof-alex]

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

SQL создавался, для накопления и анализа большого объёма данных. Вот например: http://compress.ru/Archive/CP/2006/6/72/
Подобный анализ на достаточно больших объёмах данных (а на малых что он даст?) может "положить" ООо совсем. Может это и интересно, но интерес скорее академический, т.к. OOBasic не тот инструмент, которым это следует делать.

[dr.Faust]

Это очевидно.
Однако...
Пример вычисление индикатора MACD.
Простейший случай, причём вычисляется только 1 индик, а обычно вычисляются 3-5 разных индикаторов. А среди них ест и весьма сложные особи.
С трудом представляю как сделать это средствами  SQL...

[вложение удалено Администратором]

[JohnSUN]

- ключ левого сына вершины больше или равен ключу правого ее сына...
<Часть текста skip>
... поскольку ты добавляешь элементы в массив последовательно один за другим, и на каждом шаге у тебя сохраняется целостность двоичной кучи. Добавление элемента требует максимум loq2N сравнений/перестановок и одной ячейки дополнительной памяти.

Или я чего-то упустил, или мы забываем о первоначальной задаче. Нам ведь не нужны ВСЕ значения, нам нужны только уникальные? Соответственно, меняем свойство "больше или равен" на "строго больше". И тогда вся задача сводится к заполнению кучи данными (в случае равенства элемент не добавляется) и ее обходу для получения конечного результата.
Тогда в худшем случае - все значения уникальны - куча будет того же размера, что и исходный набор данных и выходим действительно на loq2N. А если дублей много, то и размер кучи будет расти не быстро и эффективность алгоритма ещё возрастёт...
Или не так?