История изменений

Опуская детали, принцип в том, чтобы иметь чёрный массив емкостью в половину основного белого и использовать его для выполнения операций.

Ты, почти как автор темы, опустил самое важное.

Напишу тогда свой пересказ:

=== описание хранения данных ===

Экземпляр описываемой «структуры» как цельный объект (т.е. всё ниженаписанное - описание внутреннего устройства одного экземпляра) буду называть bwarr.

Данные хранятся массиве, нарезанном на фрагменты, размер каждого из которых равен pow(2,n), где n - номер фрагмента, нумерация начинается с нуля. Запишем так: frag[n] - n-ный фрагмент, frag[n][m] - m-ый элемент n-го фрагмента, при этом n>=0, 0<=m<pow(2,n). Если нужна поддержка операции удаления, то frag[n][m] должен уметь хранить как элемент, так и признак «тут ничего нет». Если не нужна, то признак пустоты нужен только фрагментам целиком, но не отдельным их элементам.

Консистентное состояние данных выглядит так: каждый из фрагментов, независимо от остальных, хранит отсортированное подмножество ранее добавленных в bwarr элементов. Чем больше номер фрагмента - тем более старые элементы в нём хранятся, то есть фрагменты, можно считать, отсортированы по времени добавления содержащихся в них элементов, но при этом сами элементы внутри одного фрагмента отсортированы по требуемому сортирующему признаку. Фрагмент может быть либо пустым (в нём нет ни одного элемента), либо содержать k элементов такое, что pow(2,n-1)<k<=pow(2,n). То есть, любой непустой фрагмент всегда заполнен более чем наполовину. Таким образом, если в bwarr ровно N=pow(2,X) элементов (X=log_2(N)), то они либо все хранятся в frag[X], либо часть из них (все не влезут) хранится в более нижних фрагментах (причём не все варианты расположения возможны). Если элементов меньше чем pow(2,X) то фрагменты с номерами больше X всё так же не могут быть непустыми.

=== описание операции поиска ===

Поиск ведётся параллельно во всех непустых фрагментах. Поскольку максимальный номер непустого фрагмента зависит от общего количества элементов N, параллельно искать придётся не более чем в ceil(log_2(N))+1 = X+1 фрагментах. Сам поиск по заранее отсортированным фрагментам делается за логарифмическое от их размера pow(2,n) (и соответственно линейное от их номера n) количество операций. Если сложить эту арифметическую прогрессию, получаем сложность поиска приблизительно пропорциональную sqr(X) = sqr(log_2(N)).

=== описание операций изменения данных ===

Для вставки и иногда для удаления используется временный буфер (почему-то там его назвали чёрным массивом), требуемый размер этого буфера равен размеру последнего из разрешённых/планируемых к использованию фрагментов (если не нужно удаление, размер временного буфера можно сделать меньше на 25%).

Вставка делается так: если frag[0] пустой, просто кладём элемент в него и завершаемся, иначе кладём вставляемый элемент во временный буфер, ставим счётчик i=0, и затем выполняем в цикле следующее:

• Делаем отсортированное слияние frag[i] и временного буфера. frag[i] после этого объявляем пустым (все элементы из него переехали в слияние). При этом, если frag[i+1] пустой, результат пишется в него и завершаемся. Иначе - результат пишется во временный буфер, счётчик i инкрементируется, идём на следующий цикл.

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

Удаление делается так: элемент (после поиска) просто помечается как пустой. Затем делается проверка: если в фрагмент до сих пор заполнен больше чем на половину (т.е. пустых мест меньше половины) - завершаемся. Если пустых мест теперь половина, а предыдущий фрагмент пустой - переносим элементы туда. Если пустых мест половина, а предыдущий фрагмент не пустой - производим сортированное слияние с ним (через временный буфер), после чего записываем результат на место текущего фрагмента (а предыдущий, из которого мы забрали элементы, объявляем пустым).

Опуская детали, принцип в том, чтобы иметь чёрный массив емкостью в половину основного белого и использовать его для выполнения операций.

Ты, почти как автор темы, опустил самое важное.

Напишу тогда свой пересказ:

=== описание хранения данных ===

Экземпляр описываемой «структуры» как цельный объект (т.е. всё ниженаписанное - описание внутреннего устройства одного экземпляра) буду называть bwarr.

Данные хранятся массиве, нарезанном на фрагменты, размер каждого из которых равен pow(2,n), где n - номер фрагмента, нумерация начинается с нуля. Запишем так: frag[n] - n-ный фрагмент, frag[n][m] - m-ый элемент n-го фрагмента, при этом n>=0, 0<=m<pow(2,n). Если нужна поддержка операции удаления, то frag[n][m] должен уметь хранить как элемент, так и признак «тут ничего нет». Если не нужна, то признак пустоты нужен только фрагментам целиком, но не отдельным их элементам.

Консистентное состояние данных выглядит так: каждый из фрагментов, независимо от остальных, хранит отсортированное подмножество ранее добавленных в bwarr элементов. Чем больше номер фрагмента - тем более старые элементы в нём хранятся, то есть фрагменты, можно считать, отсортированы по времени добавления содержащихся в них элементов, но при этом сами элементы внутри одного фрагмента отсортированы по требуемому сортирующему признаку. Фрагмент может быть либо пустым (в нём нет ни одного элемента), либо содержать k элементов такое, что pow(2,n-1)<k<=pow(2,n). То есть, любой непустой фрагмент всегда заполнен более чем наполовину. Таким образом, если в bwarr ровно N=pow(2,X) элементов (X=log_2(N)), то они либо все хранятся в frag[X], либо часть из них (все не влезут) хранится в более нижних фрагментах (причём не все варианты расположения возможны). Если элементов меньше чем pow(2,X) то фрагменты с номерами больше X всё так же не могут быть непустыми.

=== описание операции поиска === Поиск ведётся параллельно во всех непустых фрагментах. Поскольку максимальный номер непустого фрагмента зависит от общего количества элементов N, параллельно искать придётся не более чем в ceil(log_2(N))+1 = X+1 фрагментах. Сам поиск по заранее отсортированным фрагментам делается за логарифмическое от их размера pow(2,n) (и соответственно линейное от их номера n) количество операций. Если сложить эту арифметическую прогрессию, получаем сложность поиска приблизительно пропорциональную sqr(X) = sqr(log_2(N)).

=== описание операций изменения данных === Для вставки и иногда для удаления используется временный буфер (почему-то там его назвали чёрным массивом), требуемый размер этого буфера равен размеру последнего из разрешённых/планируемых к использованию фрагментов (если не нужно удаление, размер временного буфера можно сделать меньше на 25%).

Вставка делается так: если frag[0] пустой, просто кладём элемент в него и завершаемся, иначе кладём вставляемый элемент во временный буфер, ставим счётчик i=0, и затем выполняем в цикле следующее:

• Делаем отсортированное слияние frag[i] и временного буфера. frag[i] после этого объявляем пустым (все элементы из него переехали в слияние). При этом, если frag[i+1] пустой, результат пишется в него и завершаемся. Иначе - результат пишется во временный буфер, счётчик i инкрементируется, идём на следующий цикл.

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

Удаление делается так: элемент (после поиска) просто помечается как пустой. Затем делается проверка: если в фрагмент до сих пор заполнен больше чем на половину (т.е. пустых мест меньше половины) - завершаемся. Если пустых мест теперь половина, а предыдущий фрагмент пустой - переносим элементы туда. Если пустых мест половина, а предыдущий фрагмент не пустой - производим сортированное слияние с ним (через временный буфер), после чего записываем результат на место текущего фрагмента (а предыдущий, из которого мы забрали элементы, объявляем пустым).

Опуская детали, принцип в том, чтобы иметь чёрный массив емкостью в половину основного белого и использовать его для выполнения операций.

Ты, почти как автор темы, опустил самое важное.

Напишу тогда свой пересказ:

=== описание хранения данных ===

Экземпляр описываемой «структуры» как цельный объект (т.е. всё ниженаписанное - описание внутреннего устройства одного экземпляра) буду называть bwarr.

Данные хранятся массиве, нарезанном на фрагменты, размер каждого из которых равен pow(2,n), где n - номер фрагмента, нумерация начинается с нуля. Запишем так: frag[n] - n-ный фрагмент, frag[n][m] - m-ый элемент n-го фрагмента, при этом n>=0, 0<=m<pow(2,n). Если нужна поддержка операции удаления, то frag[n][m] должен уметь хранить как элемент, так и признак «тут ничего нет». Если не нужна, то признак пустоты нужен только фрагментам целиком, но не отдельным их элементам.

Консистентное состояние данных выглядит так: каждый из фрагментов, независимо от остальных, хранит отсортированное подмножество ранее добавленных в bwarr элементов. Чем больше номер фрагмента - тем более старые элементы в нём хранятся, то есть фрагменты, можно считать, отсортированы по времени добавления содержащихся в них элементов, но при этом сами элементы внутри одного фрагмента отсортированы по требуемому сортирующему признаку. Фрагмент может быть либо пустым (в нём нет ни одного элемента), либо содержать k элементов такое, что pow(2,n-1)<k<=pow(2,n). То есть, любой непустой фрагмент всегда заполнен более чем наполовину. Таким образом, если в bwarr ровно N=pow(2,X) элементов (X=log_2(N)), то они либо все хранятся в frag[X], либо часть из них (все не влезут) хранится в более нижних фрагментах (причём не все варианты расположения возможны). Если элементов меньше чем pow(2,X) то фрагменты с номерами больше X всё так же не могут быть непустыми.

=== описание операции поиска === Поиск ведётся параллельно во всех непустых фрагментах. Поскольку максимальный номер непустого фрагмента зависит от общего количества элементов N, параллельно искать придётся не более чем в ceil(log_2(N))+1 = X+1 фрагментах. Сам поиск по заранее отсортированным фрагментам делается за логарифмическое от их размера pow(2,n) (и соответственно линейное от их номера n) количество операций. Если сложить эту арифметическую прогрессию, получаем сложность поиска приблизительно пропорциональную sqr(X) = sqr(log_2(N)).

=== описание операций изменения данных === Для вставки и иногда для удаления используется временный буфер (почему-то там его назвали чёрным массивом), требуемый размер этого буфера равен размеру последнего из разрешённых/планируемых к использованию фрагментов (на самом деле, если не нужно удаление, размер временного буфера можно сделать меньше на 25%).

Вставка делается так: если frag[0] пустой, просто кладём элемент в него и завершаемся, иначе кладём вставляемый элемент во временный буфер, ставим счётчик i=0, и затем выполняем в цикле следующее:

• Делаем отсортированное слияние frag[i] и временного буфера. frag[i] после этого объявляем пустым (все элементы из него переехали в слияние). При этом, если frag[i+1] пустой, результат пишется в него и завершаемся. Иначе - результат пишется во временный буфер, счётчик i инкрементируется, идём на следующий цикл.

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

Удаление делается так: элемент (после поиска) просто помечается как пустой. Затем делается проверка: если в фрагмент до сих пор заполнен больше чем на половину (т.е. пустых мест меньше половины) - завершаемся. Если пустых мест теперь половина, а предыдущий фрагмент пустой - переносим элементы туда. Если пустых мест половина, а предыдущий фрагмент не пустой - производим сортированное слияние с ним (через временный буфер), после чего записываем результат на место текущего фрагмента (а предыдущий, из которого мы забрали элементы, объявляем пустым).

Опуская детали, принцип в том, чтобы иметь чёрный массив емкостью в половину основного белого и использовать его для выполнения операций.

Ты, почти как автор темы, опустил самое важное.

Напишу тогда свой пересказ:

=== описание хранения данных ===

Экземпляр описываемой «структуры» как цельный объект (т.е. всё ниженаписанное - описание внутреннего устройства одного экземпляра) буду называть bwarr.

Данные хранятся массиве, нарезанном на фрагменты, размер каждого из которых равен pow(2,n), где n - номер фрагмента, нумерация начинается с нуля. Запишем так: frag[n] - n-ный фрагмент, frag[n][m] - m-ый элемент n-го фрагмента, при этом n>=0, 0<=m<pow(2,n). Если нужна поддержка операции удаления, то frag[n][m] должен уметь хранить как элемент, так и признак «тут ничего нет». Если не нужна, то признак пустоты нужен только фрагментам целиком, но не отдельным их элементам.

Консистентное состояние данных выглядит так: каждый из фрагментов, независимо от остальных, хранит отсортированное подмножество ранее добавленных в bwarr элементов. Чем больше номер фрагмента - тем более старые элементы в нём хранятся, то есть фрагменты, можно считать, отсортированы по времени добавления содержащихся в них элементов, но при этом сами элементы внутри одного фрагмента отсортированы по требуемому сортирующему признаку. Фрагмент может быть либо пустым (в нём нет ни одного элемента), либо содержать k элементов такое, что pow(2,n-1)<k<=pow(2,n). То есть, любой непустой фрагмент всегда заполнен более чем наполовину. Таким образом, если в bwarr ровно N=pow(2,X) элементов (X=log_2(N)), то они либо все хранятся в frag[X], либо часть из них (все не влезут) хранится в более нижних фрагментах (причём не все варианты расположения возможны). Если элементов меньше чем pow(2,X) то фрагменты с номерами больше X всё так же не могут быть непустыми.

=== описание операции поиска === Поиск ведётся параллельно во всех непустых фрагментах. Поскольку максимальный номер непустого фрагмента зависит от общего количества элементов N, параллельно искать придётся не более чем в ceil(log_2(N))+1 = X+1 фрагментах. Сам поиск по заранее отсортированным фрагментам делается за логарифмическое от их размера pow(2,n) (и соответственно линейное от их номера n) количество операций. Если сложить эту арифметическую прогрессию, получаем сложность поиска приблизительно пропорциональную sqr(X) = sqr(log_2(N)).

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

Вставка делается так: если frag[0] пустой, просто кладём элемент в него и завершаемся, иначе кладём вставляемый элемент во временный буфер, ставим счётчик i=0, и затем выполняем в цикле следующее:

• Делаем отсортированное слияние frag[i] и временного буфера. frag[i] после этого объявляем пустым (все элементы из него переехали в слияние). При этом, если frag[i+1] пустой, результат пишется в него и завершаемся. Иначе - результат пишется во временный буфер, счётчик i инкрементируется, идём на следующий цикл.

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

Удаление делается так: элемент (после поиска) просто помечается как пустой. Затем делается проверка: если в фрагмент до сих пор заполнен больше чем на половину (т.е. пустых мест меньше половины) - завершаемся. Если пустых мест теперь половина, а предыдущий фрагмент пустой - переносим элементы туда. Если пустых мест половина, а предыдущий фрагмент не пустой - производим сортированное слияние с ним (через временный буфер), после чего записываем результат на место текущего фрагмента (а предыдущий, из которого мы забрали элементы, объявляем пустым).