realloc(3) в стиле common lisp

[swizard]

Одну из самых востребованных на рынке структур данных: "массив" можно получить в CL с помощью функции make-array. В принципе, зачастую этой информации достаточно для успешного и счастливого применения массивов в практике.

Но если копнуть немного поглубже, неожиданно выясняется, что, в зависимости от переданных параметров, make-array умеет

Comments

[thedeemon]

Фигасе разница, там что обычный вектор - это список что-ли?

Нельзя ли сделать более приличный вектор как в скале и кложуре (32-арное дерево) и, пользуясь динамиченостью лиспа, сделать так, чтобы он везде использовался вместо того медленного вектора?

[swizard]

Не, там не список, но что-то с реаллокацией (в профайлере виден replace -- это типа лисповый memcpy).

А зачем дерево для вектора, если вся фишка вектора в O(1) доступе?

[thedeemon]

Там фишка в том, при массиве на миллиард значений (4 гига интов например) у 32-ного дерева глубина будет всего 6 или 7, что "почти О(1)". Зато мгновенные конкатенация, взятие подмассива и добавление с обоих сторон.

[swizard]

А на четыре гига интов там случайно не будет 256 гигов ссылок от каждого узла на своих детей? :)

[thedeemon]

Нет, узлы и листья по-разному устроены.

[swizard]

Все равно должен быть хотя бы четырехкратный оверхед по памяти по сравнению с обычным массивом, ну или я что-то не понимаю

[thedeemon]

Не вижу, откуда взяться четерехкратному или хотябы четвертькратному.
У нас дерево, где все ветви одной длины. В самом низу, в листьях, unboxed массивы по 32 значения, например int[32]. В узлах выше unboxed массивы по 32 указателя вниз. Плюс отдельно несколько общих переменных - высота дерева, начало, конец. Оверхед ~ 1/32 + (1/32)^2 + (1/32)^3...