booby,
ладно, хоть andrey_anonymous и не захотел "делиться своими секретами",
из топика надо как-то разумно выходить, раз уж влез в него.
Решил накидать модель того, что в предыдущем посте было названо "сложением по Кислицкому",
поскольку вряд ли что-то вообще гуглится по такому названию, и вряд ли каждый из прочитавших немедленно понял, о чем идет речь.
идея "отсортировать и сложить" состоит в первую очередь в сложении сначала малых значений,
образуя из них такую текущую сумму, которая, по вероятности, не потеряется при сложении со следующими б
о льшими значениями в складываемом потоке.
Но это по настоящему хорошо работает лишь на некоторых потоках данных, не говоря о затратах на сортировку.
Альтернативную идею можно сформулировать так:
1) образуй частичные суммы
2) складывай между собой такие частичные суммы, которые испытали до этого одно и то же количество сложений.
Из такой формулировки выводится две несхожие реализации, одна из которых в статье
англоязычной википедии о сложении по Кахану названа попарным сложением,
а другая не упоминается.
Общего между ними то, что в обоих случаях образуется двоичное дерево вычислений одной и той же высоты.
Общее число сложенных элементов определяется как 2 в степени высоты дерева.
Высота 64 достаточна для сложения 2**64 слагаемых, что выглядит как с большим запасом достаточное количество для использования в обычных базах данных (18 446 744 073 709 551 616 слагаемых).
64 - это оценка максимальной глубины рекурсии попарного сложения, построенного на рекурсивном методе "разделяй и властвуй", и это же оценка необходимого количества "ячеек" дополнительной памяти, в которые складываются частичные суммы во втором методе.
То есть использование дополнительного массива в 64 элемента обеспечивает достаточно
места для сложения результатов, определяемых частичными суммами, испытавшими одно и то
же число сложений. этот массив можно назвать "счетчиком сложений", хранящим результаты самих частичных сложений - т.е. простейшими счетами - абаком, в ячейки которого складываются частичные суммы.
В отличие от метода "попарных сумм" такой заход обеспечивает отсутствие рекурсии,
высокую степень локальности хранимых данных, легко приспосабливается к работе в параллельном окружении, и годен для работы с потоковыми данными.
При одной и той же асимптотической производительности и одинаковых
статистических характеристиках нарастания ошибки, он должен несколько быстрее работать именно на массивах, а на потоках попарное сложение ему не конкурент.
Сейчас набросал вариант реализации для binary_double чисел, для которых алгоритмы подомного сорта и предназначены.
Определим на схеме коллекцию числе binary_double:
1.
Create or replace Type T_TAB_BDOUBLE as table of binary_double;
Работу счетчика сложим в объект:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
create or replace type t_bdouble_sumcounter as Object (
-- суммирование binary_double на двоичном счетчике-абаке
a_counter T_TAB_BDOUBLE,
-- конструктор по умолчанию
constructor function t_bdouble_sumcounter(Self in out nocopy t_bdouble_sumcounter) return Self as result,
-- добавление слагаемого в счетчик
-- pd_amount in Binary_Double - добавляемое слагаемое
-- p_carry out binary_double - сумма после переполнения старшего разряда, иначе ноль
member procedure put(Self in out nocopy t_bdouble_sumcounter, pd_amount in Binary_Double, p_carry out binary_double),
-- съем текущей суммы со счетчика
member function get_sum(Self in out nocopy t_bdouble_sumcounter) return binary_double
)
/
create or replace type body t_bdouble_sumcounter is
-- конструктор по умолчанию
constructor function t_bdouble_sumcounter(Self in out nocopy t_bdouble_sumcounter) return Self as result
Is
-- размер счетчика
ci_MaxLen constant pls_integer := 64;
Begin
self.a_counter := new T_TAB_BDOUBLE();
self.a_counter.Extend(ci_MaxLen);
Return;
End;
-- добавление слагаемого в счетчик
-- pd_amount in Binary_Double - добавляемое слагаемое
-- p_carry out binary_double - сумма после переполнения старшего разряда, иначе ноль
member procedure put(Self in out nocopy t_bdouble_sumcounter, pd_amount in Binary_Double, p_carry out binary_double)
is
cdbl_Zero constant binary_double := 0.0D;
i pls_integer;
tmp_sum binary_double;
Begin
p_carry := cdbl_Zero;
If pd_amount is null Then Return; End If;
-- проверка стартового разряда
i := Self.a_counter.First;
If Self.a_counter(i) Is Null
Then
Self.a_counter(i) := pd_amount;
Return; -- ранний возврат
End If;
-- здесь оказываемся, только когда первый разряд занят значением
tmp_sum := pd_amount ;
-- складываем и переносим заполненные разряды
While Self.a_counter(i) is not Null
Loop
tmp_sum := tmp_sum + Self.a_counter(i);
Self.a_counter(i) := Null;
i := Self.a_counter.Next(i);
Exit When i Is Null;
End Loop;
If i Is Not Null
Then -- формируем значение для следующего разряда
Self.a_counter(i) := tmp_sum;
Else
-- переполнение счетчика, формируем p_carry
p_carry := tmp_sum;
End If;
End;
-----------------------------------------------------------------
-- съем текущей суммы со счетчика
member function get_sum(Self in out nocopy t_bdouble_sumcounter) return binary_double
is
cdbl_Zero constant binary_double := 0.0D;
i pls_integer;
dbl_result binary_double;
Begin
i := self.a_counter.First;
<<OUTER_L>>
While i is Not Null
Loop
-- пропуск пустых значений
While self.a_counter(i) is Null
Loop
i:= self.a_counter.Next(i);
Exit OUTER_L When i is Null;
End Loop;
-- накопление результата
dbl_result := Coalesce(dbl_result, cdbl_Zero) + self.a_counter(i);
i:= self.a_counter.Next(i);
End Loop;
Return dbl_result;
End;
End;
/
Параметр p_carry процедуры put в норме возвращает ноль.
Как только он вернул не ноль, это значит, что разрядной сетки счетчика не хватило
для поддержки высоты вычисления, и с полученным числом вызывающий клиент дальше
должен обходиться самостоятельно - разрядная сетка счетчика переполнилась.
Вокруг этого, например, легко далее написать оператор специального сложения с помощью дополнительного объекта,
и такой счетчик сможет поддержать в этом операторе параллельность работы естественным образом.
Этот вариант настолько же лучше попарного сложения, насколько менее известен и совсем не описан в публичных википедиях.
PS1
Почему использовал название "сложение по Кислицину"
На ютубе как-то набрел на ролики, обсуждающие алгоритм Кислицина поиска наименьшего и следующего за ним наименьшего, упоминаемый в 17 томе УМН 1962г. (Успехи математических наук) в заметках о заседаниях Ленинградского математического общества.
(сам алгоритм в УМН не приводится, но дается асимптотическая оценка его сложности).
Двоичный счетчик существенно используется в том алгоритме, но в более сложном конструктивном исполнении.
Мимоходом при обсуждении в ролике на ютубе сказано, что с такими счетчиками можно делать много полезных вещей, простейшей из которых является сложение чисел с плавающей точкой с хорошими статистическими характеристиками и по скорости нарастания ошибки
и по общей производительности.
Т.е., в своей идее, это уже очень старый алгоритм.
Возможно уже "ненужный" или даже "бесполезный" в контексте обнаружения метода Ноймайера.
За сим из топика выхожу.
PS2
надеюсь, топикстартер не сильно обижен за такое замусоривание его топика.
