Рефераты | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics | страница реферата 1 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы


    • Рефераты | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics


    Рефераты | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics

    Создание эффективной реализации сортированного списка с использованием generics




    Категория реферата: Рефераты по информатике, программированию
    Теги реферата: реферат мова, изложение язык
    Добавил(а) на сайт: Bajdavletov.



    1  2  3  4  5  6  7  8  9  10  11 |



    Создание эффективной реализации сортированного списка с использованием generics

    Сергей Смирнов (Serginio1)

    Так случилось, что я стал программистом 1С. Все прекрасно в этой среде, за исключением скорости. Эту проблему можно решить только одним способом: прямым доступом к файлам и обработкой результатов на компилируемом языке в памяти.

    Так, для группирования данных нужны алгоритмы поиска и вставки. И мое сознание, отягощенное бухгалтерским учетом, не нашло ничего лучшего, чем использовать аналог TList (SortedList), представляющий собой динамический массив со свойствами «емкость» и «количество элементов».

    Упорядоченность в этом массиве поддерживается с помощью компараторов, а при поиске используется алгоритм половинного деления с поиском нужной позиции i по ключу с условием (Items[i]>=Key) AND (Items[i-1]<Key). Если такого ключа нет, то все данные с позиции i переносятся на одну позицию в большую сторону. При этом используются процессорные команды MOVSW и MOVSB, которые выполняются очень быстро. При полном заполнении массива его размер увеличивается либо за счет свободных адресов, следующих за конечным адресом в массиве, либо с помощью выделения нового массива большей емкости с копированием данных из оригинала.

    Но время шло, и объем группировок вышел за 10000 записей. Мой AMD K6 200 (мощный по тем временам компьютер) начал работать слишком меленно. И не удивительно – количество сдвигаемых элементов в среднем стало равно N2/4, то есть 108.

    И вот как-то, после очередного обучения бухгалтеров бухгалтерии, пришла мысль. Зачем держать один большой массив, если можно его разбить на множество маленьких? Сказано – сделано. В течение двух минут я создал двухуровневый массив. Первый (верхний) уровень – это массив, элементами которого являются ссылки на массивы нижнего уровня. Второй из уровней (нижний) по сути, состоит из простых динамических массивов. Под простыми понимается то, что память под них выделяется заранее и впоследствии не перезанимается. Фактически этот массив представляет собой структуру, хранящую счетчик элементов и массив пар «ключ-значение». В дальнейшем я буду называть эти динамические массивы листовыми страницами (LeafPage).

    PLeafPage=^ TLeafPage;

      TLeafPage = Record

      // количество задействованных элементов в массиве KeyItems

      Count:Integer;

      // массив ссылок на пары «ключ-значение»

      KeyItems:Array[0..63] of Tobject;

    End;

    TLeafPageArray = Array of PleafPage;

    LeafPageArray : TLeafPageArray;

    Поиск проходил в 2 этапа. Сначала производится поиск массива, в котором может находиться искомый ключ. Для этого с искомым значением сравниваются значение ключей нулевых элементов массивов KeyItems с таким условием, чтобы значение ключа нулевого элемента массива было меньше или равнялось искомому, а значение нулевого элемента следующего массива превышало искомое.

    Это можно выразить так:

    (LeafPageArray[j].KeyItems[0] <= Key)

     AND (LeafPageArray[j+1].KeyItems[0] > Key)

    Алгоритм поиска на нижнем уровне аналогичен поиску в одномерном массиве. При полном заполнении KeyItems выделяется новый PLeafIPage, в который копируется половина данных. Ссылка на новый массив вставляется в массив LeafPageArray в позицию на 1 больше текущей. При этом количество кода было менее 100 строк.

    Такой подход позволил резко сократить объем копируемой памяти – так как количество копируемых элементов никогда не превышает 64. Тем самым удалось избежать замедления работы массива при его росте.

    ПРИМЕЧАНИЕ

    И не удивительно, т.к. количество переносимых элементов стало равно (N / 64) * 642 / 4 + (N / 64)2 / 4 = N * k / 4 + (N / k)2 / 4. Здесь к – емкость страницы, но учитывая, что страницы заполняются не полностью, смело можно составить приблизительную формулу расчета общего количества операций копирования: N * k / 2 + (N / k)2 / 2, оптимальное значение К будет K(N) = (2N)-3, и соответственно, 643 – вполне приемлемый размер страницы для хранения данных в этом классе. Отношение количества копируемых элементов в одномерном массиве к двухуровневому составило N / (k + N / k2) / 2. В любом случае это отношение очень велико. Единственный минус этого алгоритма в замедлении поиска, так как доступ к ключу производится через дополнительную ссылку. Для исправления этого недостатка достаточно включить нулевой элемент KeyItems в структуру родительского массива.

    TNodeItem = Record

      Key : Tobject;


    Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, личные сообщения.



    1  2  3  4  5  6  7  8  9  10  11 |




    Поделитесь этой записью или добавьте в закладки

       

    Категории:



    Разделы сайта




    •