#структуры
Можно ли реализовать список на базе массивов, от которого требуется: Не константный размер (заранее неизвестен, может расширяться). Время вставки было О(1) или около того. Посмотрел реализацию в Java. Там получается, что вставка работает за O(1) во всех случаях, кроме случая, когда требуется расширение массива (в этот момент из-за копирования получается O(N)), где массив расширяется в 1,5 раза. Требуется же, чтобы работа операции вставки в конец работала во всех случаях за константное время.
Ответы
Ответ 1
Пошел дождь, планы изменились, я набросал простейшую реализацию. Ее, конечно, еще тестировать надо, но если кому интересно, выкладываю код. Прошу извинения, он довольно большой, но как поместить код куда нибудь и дать здесь ссылку на него, я не знаю. /* avp 2011 Динамический массив размером до 2^32 элементов. По сути структура MMU с динамическим выделением сегментов данных и блоков оглавления нижнего уровня. Оглавление всегда 2 уровня. Структура 32-разрядного адреса: 10 бит индекс в корневом блоке оглавления 10 бит индекс в блоке сегментов памяти 12 бит индекс элемента в сегменте данных Корневой блок, нулевой блок сегментов и нулевой сегмент создаются сразу при создании динамического массива. struct dyna *dyna_init (int elem_size); Создать массив с нулевым сегментом 4096 элементов размером elem_size байт каждый. Дескриптор (struct dyna) выделяется malloc(). void dyna_free (struct dyna *dyna); Освободить всю память массива и дескриптор. void *dyna_get (struct dyna *dyna, unsigned int index); Возвращает адрес DynArray[index] или NULL (нет памяти). При первом обращении память под соответствующий сегмент данных выделяется автоматически. Массив в середине может содержать 'дыры' (аналогично файлу в Unix). void *dyna_segment (struct dyna *dyna, unsigned int index); Возвращает адрес начала сегментв данных размером 4096 элементов динамического массива, содержащий элемент с индексом index. Если сегмента нет (дыра, обращений к эдементам массива, входящих в этот сегмент не было), то возвращаем NULL. По большому счету, надо использовать posix_memalign() вместо malloc(), НО в MinGW ее нет. */ #include#include struct dyna { void **root; // адресуем по старшим 10 бит. unsigned int maxindex; // максимальный размещенный индекс. int elem_size; // елемент данных в байтах. }; #define DEBUG 1 struct dyna * dyna_init (int elem_size) { struct dyna *dyna = malloc(sizeof(*dyna)); if (!dyna) return NULL; // Тут по хорошему надо exit(), ну и далее тоже. if (!(dyna->root = calloc(1024,sizeof(void *)))) return NULL; if (!(dyna->root[0] = calloc(1024,sizeof(void *)))) return NULL; char **table = dyna->root[0]; // первый сегмент данных if (!(table[0] = calloc(4096,dyna->elem_size=elem_size))) return NULL; dyna->maxindex = 4095; return dyna; } void dyna_free (struct dyna *dyna) { int i; char **tab; for (i = 0; i < 1024; i++) { if (tab = dyna->root[i]) { int j; for (j = 0; j < 1024; j++) { if (tab[j]) free(tab[j]); } free (tab); } } free(dyna->root); free(dyna); } void * dyna_segment (struct dyna *dyna, unsigned int index) { int rix = (index >> 22) & 0x3ff, tix = (index >> 12) & 0x3ff; char **tab; if (tab = dyna->root[rix]) return tab[tix]; return NULL; } void * dyna_get (struct dyna *dyna, unsigned int index) { int rix = (index >> 22) & 0x3ff, tix = (index >> 12) & 0x3ff, dix = index & 0xfff; char **tab; if (tab = dyna->root[rix]) { if (!tab[tix]) if (!(tab[tix] = calloc(4096,dyna->elem_size))) return NULL; // Беда // OK tab[tix] содержит адрес сегмента данных с index. } else { // делаем таблицу сегментов и сегмент данных if (!(tab = dyna->root[rix] = calloc(1024, sizeof (void *)))) return NULL; // Совсем беда if (!(tab[tix] = calloc(4096,dyna->elem_size))) return NULL; // Опять беда } // OK tab[tix] содержит адрес сегмента данных с index. // char *dat = tab[tix]; // segment addr if (index > dyna->maxindex) dyna->maxindex = ((index+4096) & 0xfffff000)-1; return tab[tix] + dix * dyna->elem_size; } #if DEBUG main () { struct dyna *dar; int *pi, i, *ps, nn[10]; dar = dyna_init(sizeof(int)); if (dar) { printf ("root = 0x%x, maxi = %d, esiz = %d\n", dar->root, dar->maxindex, dar->elem_size); } char **tab = dar->root[0]; printf ("root[0] = 0x%x, tab[0] = 0x%x, tab[1] = 0x%x, segm[0] = 0x%x\n", tab,tab[0],tab[1],dyna_segment(dar,5)); printf ("segm[0](0) 0x%x; segm[0](2000) 0x%x; segm[0](4095) 0x%x; segm[1](4096) 0x%x; segm[?](100000) 0x%x\n", dyna_segment(dar,0),dyna_segment(dar,2000),dyna_segment(dar,4095), dyna_segment(dar,4096),dyna_segment(dar,100000)); pi = dyna_get(dar,i = 4097); printf ("root = 0x%x, maxi = %d, esiz = %d\n", dar->root, dar->maxindex, dar->elem_size); printf ("tab[0] = 0x%x, tab[1] = 0x%x, segm[1] = 0x%x, pi = 0x%x, *pi = %d\n", tab[0], tab[1], ps = dyna_segment(dar,i), pi, *pi); for (i = 0; i < 3; i++) ps[i] = i+10; printf ("ps = 0x%x\n",ps); for (i = 4096; i < 4099; i++) { pi = dyna_get(dar,i); printf ("i = %d pi = 0x%x *pi = %d\n",i,pi,*pi); nn[i-4096] = *pi; } for (i = 0; i < 3; i++) printf ("nn[%d] = %d ",i,nn[i]); putchar('\n'); printf ("segm[0](0) 0x%x; segm[0](2000) 0x%x; segm[0](4095) 0x%x; segm[1](4096) 0x%x; segm[2](8192) 0x%x\n", dyna_segment(dar,0),dyna_segment(dar,2000),dyna_segment(dar,4095), dyna_segment(dar,4096),dyna_segment(dar,8192)); dyna_free (dar); printf ("End\n"); exit (0); } #endif Результаты того, что я запускал, выглядят вполне разумными. Если кто найдет ошибки, буду признателен. Ответ 2
Это не ответ, а некоторые соображения 'по поводу'. Итак, допустим требуется: массив может расти 'вперед', новые элементы добавляются в конец, время доступа по индексу O(1), занимаемое массивом пространство непрерывно и при этом расширение массива тоже требует времени O(1). Если отбросить непрерывность на всем протяжении, то можно представить набор массивов (сегментов нашего виртуального массива). Эти сегменты д.б. достаточно большими (тысячи элементов). Этот список может только расти. При появлении второго и следующих сегментов делаем оглавление. Вначале оглавление это один сегмент (один уровень косвенности). Каждый элемент оглавления ссылается (по адресу) на первый элемент соответствующего сегмента с элементами массива. Таким образом оглавление из одного сегмента размером N адресует N*N элементов массива. Очевидно все адреса вычисляются за O(1). Добавление сегментов памяти в массив тоже O(1). Дальнейший рост массива приводит к появлению следующих уровней оглавления. Два уровня позволяют адресовать N*N*N элементов массива за три вычисления адреса. При N = 1000 два уровня оглавления адресуют миллиард элементов массива. Разумеется к элементам такого "массива" не получится обращаться по традиционной записи Arr[i]. Для работы с элементами надо разработать удобный набор функций. Это, конечно, достаточно общие соображения на скорую руку. Надеюсь, хоть частично угадал, что требовалось.Ответ 3
Не знаю почему никто не упомянул std::deque, в отличие от std::vector при добавлении не делает realloc, соответственно работает быстрее. Если элементом очереди будет < data, next >, то порядок следования становиться не важен... P.S. мне кажется, что-то похожее описывал @avp в своем ответеОтвет 4
Если я правильно поняла вопрос, то можно использовать "теневое" копирование. Т.е. при "расширении" копировать элементы по шагам (несколько элементов при каждой вставке). У нас есть 2 массива: Массив длины N, в который добавляются элементы (активный). Массив большей длины, например, 2*N, который находится в стадии заполнения. Мы будем добавлять элементы в первый массив. Далее, когда он заполнится на 0,75*N (например), начнем копировать по несколько элементов в массив большей длины. Конечно, количество скопированных элементов за один шаг должно быть выбрано таким образом, чтобы копирование завершилось до переполнения старой структуры структуры :) Возьмём, количество элементов за шаг = 4 (K). Когда элементы меньшего массива полностью скопированы в новый, больший по размеру массив, старый массив удаляется, а новый принимается в качестве активной структуры. Далее (при необходимости) снова создается массив большей длины. Получится, что доступ к элементам останется O(1), а для добавления элемента понадобится 5 действий (K+1) в худшем случае. А значит, добавление в конец списка будет работать за линейное время всегда. Такая структура, по-моему, удовлетворяет условиям, но будет занимать больше памяти.
Комментариев нет:
Отправить комментарий