Когда опасно иметь слишком много динамических массивов?

Question

Когда опасно иметь слишком много динамических массивов?

В настоящее время я пишу код для задания, которое касается городов и мостов. Я должен напечатать города и мосты в их уважаемых районах, таких как:

//unorganized inputs from user given the # of "paths" we need
4       // the # of paths
1 2 5  // 1 = city , 2 = city, 5 = bridge length
6 7 5  // 6 = city , 7 = city, 5 = bridge length
2 3 7  // 2 = city , 3 = city, 7 = bridge length
6 9 7  // 6 = city , 9 = city, 7 = bridge length

После запуска программы она будет отсортирована как:

first district
1 2 5
2 3 7

2nd district
6 7 5
6 9 7

Теперь я буду читать эти материалы через cin. Я хочу сохранить все возможные пути, такие как 1 2 5 в массив, а затем отсортировать и организовать их через программу. Проблема в том, что у меня может быть более 500 000 путей от пользователя. Я хочу создать 500k динамических массивов. Не вызовет ли это серьезных проблем с памятью?

Я рассмотрел другие возможные способы решения этой проблемы, такие как алгоритм Крускала и непересекающиеся множества (я думаю, что это наиболее полезно). Мне очень тяжело разбираться в кодировании непересекающихся множеств, я решил, что попробую способ, с которым я более знаком.

Любая помощь в том, где хранить значения, сравнивать и систематизировать их, была бы полезна. Ссылки на места, где я читаю информацию об этом, помогут. Я много читал за последние несколько дней. Не сильно помогло.

Подводя итог, мои вопросы:

Будут ли динамические массивы 500 КБ вызывать серьезные проблемы с точки зрения памяти?
Где хранить значения, сравнивать и систематизировать их по заданным путям?

3

arrays c++disjoint-sets dynamic

Решение

Другие решения

В целом, при условии, что у вас есть 2 гигабайта памяти для вашего приложения, 500K записей по 12 байт (при условии, что вы используете 32 бита для своих значений) не будет проблемой.
Если вы хотите уменьшить размер набора данных, вы можете, например, использовать формат данных, например:

struct {
unsigned short city_a;
unsigned short city_b;
char length;
}

Посмотрите на размер набора городов (количество городов) и максимальную длину между двумя городами.
Кроме того, такие вещи, как индексация пар городов (A-B становится Pair_ID), также могут уменьшить набор данных.

1

Возможно, это не имеет прямого отношения к вашему вопросу, но я думаю, что вы пытаетесь достичь этого — http://en.wikipedia.org/wiki/Connected_component_(graph_theory). И если вы моделируете свой граф как матрицу смежности, вам не нужно выделять 500 тыс. Динамических массивов. Рассмотрим следующий формат для хранения ваших данных:

int city_map [MAX_NO_OF_CITIES][MAX_NO_OF_CITIES];

city_map[i][j] = length_of_brigde_connecting_city_i_to_j;

Таким образом, хранение 500 000 записей займет чуть более 1 МБ памяти.

1

Источник

Accepted Answer

Будут ли динамические массивы 500 КБ вызывать серьезные проблемы с точки зрения памяти?

Нет проблем, если предположить, что каждый из них представляет собой массив из 3-х целых. Как правило, вы избегаете делать это как отдельные выделения, потому что это чрезмерно — это будет немного медленным, а требуемая бухгалтерия будет также потреблять достаточное количество памяти. Есть лучший подход:

Где хранить значения, сравнивать и систематизировать их по заданным путям?

Я бы начал с struct / class, которая содержит эти 3 поля, а затем использовал бы std::vector из тех. Это сохранит все ваши значения как одно непрерывное распределение. Очень быстро создавать, искать и размещать в сравнении.

1