Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 12
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 25
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 25
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 26
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 26
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 27
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 27
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 28
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 28
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 29
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 25
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 25
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 26
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 26
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 27
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 27
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 28
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 28
Deprecated: Function eregi() is deprecated in /home/codingr/sites/codingrus.ru/maincore.php on line 29
.:: CodingRUS ::. программирование по-русски на Delphi, C++, PHP, Prolog, GPSS
10.1. Массив точек
Прислано vovan666 на April 17 2013 00:01:35
На этом рисунке точка 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