В реальной системе скорость поиска точек была важна для взаимодействия с пользователем
В реальной системе скорость поиска точек была важна для взаимодействия с пользователем и для других функций, которые пользовались тем же интерфейсом для своих целей. Если бы время доступа не имело значения, мы могли бы добавить в структуру данных точки обе ее координаты и достигли бы максимального уменьшения объема, по нам приходилось бы последовательно перебирать пх все для проверки наличия точки с данными координатами. Даже если не добавлять в структуру точки эти поля, объем памяти структуры можно уменьшить до 4000 байт с помощью «ключевой индексации»: поиск осуществляется в массиве, i-й элемент которого содержит 2 поля по 1 байту, в которых записаны значения row и col точки i.
Этот пример иллюстрирует несколько основных моментов, связанных со структурами данных. Мы имеем дело с классической задачей о представлении разреженного массива (разреженным массивом называется такой массив, в котором большая часть элементов имеет одно и то же значение, обычно пулевое). Решение просто по смыслу, и его легко реализовать. Мы используем несколько способов экономии памяти. Нам не приходится заводить отдельный массив для хранения последнего элемента в столбце, поскольку он идет непосредственно перед первым элементом в следующем столбце. Это типичный пример, в котором некоторая величина вычисляется заново, вместо сохранения ее в памяти. Аналогично, нет необходимости в массиве row, если есть массив col, потому что к последнему мы обращаемся только через массив firstincol, а значит, мы всегда знаем, в каком столбце мы находимся. Хотя мы начали с 32-разрядного представления для массива row, мы затем сократили разрядность до 16 и даже до 8 бит. Мы начали е записей, но в конце концов вернулись к массивам, попутно экономя по килобайту памяти то в одном месте, то в другом.
Опубликовал vovan666
April 17 2013 00:01:41 ·
0 Комментариев ·
3194 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
