На этом рисунке точка 17 имеет координаты (0, 2), точка 538 — (0, 5), а остальные места в первом столбце пусты.
Массив было легко описать в программе, и он обеспечивал быстроту доступа. Программисту пришлось выбирать между 32- и 16-разрядными целыми. Если бы он выбрал 32-разрядные, массив из 200*200 = 40 000 элементов занял бы 160 Кбайт памяти. Поэтому программист выбрал более краткое представление, и массив занял 80 Кбайт, то есть 1/6 часть памяти объемом в половину мегабайта. В начальный период использования системы никаких проблем не возникало. Однако с ростом системы начались проблемы с памятью. Программист попросил меня помочь уменьшить объем памяти, занимаемый этой структурой. Что бы вы ему посоветовали?
Эта задача — классический пример на использование разреженных структур данных. Пример относится к далекому прошлому, но недавно мне пришлось столкнуться с аналогичной проблемой представления матрицы 10 000x10 000 с миллионом активных элементов в 100 Мбайт памяти.
Очевидный способ представления разреженных матриц состоит в создании массива, соответствующего столбцам матрицы, и связных списков, содержащих активные элементы в соответствующих столбцах. Рисунок 10.2 пришлось повернуть на 90° по часовой стрелке, чтобы он лучше уместился в книге.
pointnum
colhead row . next
Опубликовал vovan666
April 17 2013 00:01:35 ·
0 Комментариев ·
3623 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
