Четырёхмерные и больше массивы (Не слишком ли большие у меня запросы?)

Модератор: Модераторы разделов

promov
Сообщения: 384
Статус: Участник
ОС: Debian GNU/Linux

Четырёхмерные и больше массивы

Сообщение promov »

...А меж тем я нашёл им даже очень подходящее применение. Хотя, глупо думать, что я первый. Но всё по порядку.

Я работаю с рядом одномерных массивов элементов типа int. Естественно, удобно расположить их в одном месте- в двумерном массиве, что я и делаю. Срочка- массив. Строчка- массив.
И вот эти вот строчки идентифицируются у меня по первым четырём элементам. Лопустим, первые четыре элемента: x, y, z, w. А всего элементов больше, штук 7. Так, строчку двумерного массива мы без труда этими элементами заполним. Но вот как к ней в случае необходимости обратиться? Если, повторяю, идентификация строчки- по первым 4-ём элементам? По номеру стоки? А к чему его привязывать? Опять же к этим 4-ём элементам? А не проще ли сделать так:

Создаётся массив int* mass2 [m] [m] [m] [m], где m- достаточно большое число (вы уж простите меня за стоь невнятную формулировку. Для каждой конкретной задачи каждый сам определит для себя m). И после заполнения очередной строчки массива mass1

Код: Выделить всё

 mass2 [h] [0]= x;
  mass2 [h] [1]= y;
mass2 [h] [2]= z;
mass2 [h] [3]= w;
mass2 [h] [4]= ...<Здесь некоторое значение типа int>
mass2 [h] [5]= ...<Здесь некоторое значение типа int>
mass2 [h] [6]= ...<Здесь некоторое значение типа int>

Добавляем

Код: Выделить всё


mass2 [x] [y] [z] [w]= &mass2 [h] [0]

(Обратите внимание, h- номер строки, но его числовое значение не важно. Он просто должени инкременироваться после инкриминации каждой строки и всё)

Всё, адрес нулевого элемента нужной строки известен, при желании можно всегда найти и последующие:

Код: Выделить всё

 * (mass2 [x] [y] [z] [w]+ <какое-то число от 0 до 6>)

Всё. Недостатки такого способа: массив mass2 будет заполнен не полностью. Много элементов просто не нужно будет.

Теперь: с трёхмерным массивом такой способ проходит на "ура". А вот с четырёхмерным как быть? Простого тестирования программы будет явно недостаточно- тут нужно знать подноготную. Вот я и обращаюс к вам: может, есть среди вас те, кто собаку съел на этом деле- стоит или нет браться за подобную идентификацию строк?

Спасибо.
Зачем хорёк пошел в ларёк, зачем барсук полез на сук...
Мораль легко уразуметь: зачем на бал пришёл медведь?
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5489
ОС: Gentoo

Re: Четырёхмерные и больше массивы

Сообщение /dev/random »

promov писал(а):
08.04.2008 20:15
Теперь: с трёхмерным массивом такой способ проходит на "ура". А вот с четырёхмерным как быть? Простого тестирования программы будет явно недостаточно- тут нужно знать подноготную. Вот я и обращаюс к вам: может, есть среди вас те, кто собаку съел на этом деле- стоит или нет браться за подобную идентификацию строк?

Не стоит. При m=256 (достаточно большое?) массив int *a[m][m][m][m] займет на x86 16GB (т.е не влезет в адресное пространство), а на x86_64 - 32GB. Лучше использовать хеш.
Спасибо сказали:
promov
Сообщения: 384
Статус: Участник
ОС: Debian GNU/Linux

Re: Четырёхмерные и больше массивы

Сообщение promov »

Так, конкретно для моей задачи m== 48. Не больше. Скажите пожалуйста, я не понял, как Вы подсчитали. Сколько у меня займёт адресного пространства массив mass2?
А что такое хеш, я не знаю
:грустящий человечек:
Зачем хорёк пошел в ларёк, зачем барсук полез на сук...
Мораль легко уразуметь: зачем на бал пришёл медведь?
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5489
ОС: Gentoo

Re: Четырёхмерные и больше массивы

Сообщение /dev/random »

1) size(m, bits)=m4*bits/8 (bytes)
size(256,32)=16 GB
size(256,64)=32 GB
size(48,32)= около 20 MB (тоже многовато)

2) Wikipedia: Hash table
Спасибо сказали:
Аватара пользователя
azrael
Сообщения: 73
ОС: KUbuntu 8.04 Hardy Heron

Re: Четырёхмерные и больше массивы

Сообщение azrael »

promov, да можете хоть десятимерные создавать, если мозга не жалко :) 4-мерный массив принципиально ничем от 3-мерного не отличается. Через полгода откроете исходник и спросите "это я писал?!" :)
Насчет размера все верно, подобный способ идентификации строк не оправдан ничем, кроме разве учебных целей)
Спасибо сказали:
promov
Сообщения: 384
Статус: Участник
ОС: Debian GNU/Linux

Re: Четырёхмерные и больше массивы

Сообщение promov »

azrael писал(а):
12.04.2008 11:55
promov, да можете хоть десятимерные создавать, если мозга не жалко
Не жалко. Ибо, как я показал, это просто. Создаётся просто, заполняется посто, указатели в нём ищутся ещё проще.

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

И ещё: я уверен, что мы обойдёмся без указания на безусловные недостатки моего способа. Тем более, что я на них сам уже указал и dev/random указал.

...Да, и ещё: вот это Вы к чему?
azrael писал(а):
12.04.2008 11:55
4-мерный массив принципиально ничем от 3-мерного не отличается.
Зачем хорёк пошел в ларёк, зачем барсук полез на сук...
Мораль легко уразуметь: зачем на бал пришёл медведь?
Спасибо сказали:
Аватара пользователя
azrael
Сообщения: 73
ОС: KUbuntu 8.04 Hardy Heron

Re: Четырёхмерные и больше массивы

Сообщение azrael »

Да не надо ждать от всех враждебности, я всего лишь ответил на ваш вопрос :)

А вот с четырёхмерным как быть? Простого тестирования программы будет явно недостаточно- тут нужно знать подноготную.
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5489
ОС: Gentoo

Re: Четырёхмерные и больше массивы

Сообщение /dev/random »

promov писал(а):
12.04.2008 15:47
Но Вы, наверное, знаете другой способ идентификации строк двумерного массива по нескольким известным элементам. Не менее, а скорее всего, даже более эффективный.

Я уже сказал. Хеш. А можно поисковые деревья.
И то, и другое, кстати, уже реализовано в стандартной библиотеке C++ (hash_map/hash_multimap и map/multimap соответственно)
Спасибо сказали:
promov
Сообщения: 384
Статус: Участник
ОС: Debian GNU/Linux

Re: Четырёхмерные и больше массивы

Сообщение promov »

Странно это всё. Нет, что ли, умных русских парней? Всё везде сплошь на английском!
Зачем хорёк пошел в ларёк, зачем барсук полез на сук...
Мораль легко уразуметь: зачем на бал пришёл медведь?
Спасибо сказали:
allez
Сообщения: 2223
Статус: Не очень злой админ :-)
ОС: SuSE, CentOS, FreeBSD, Windows

Re: Четырёхмерные и больше массивы

Сообщение allez »

А что странного? Умные русские парни хорошо знают английский язык и не нуждаются в переводе. Это во-первых. А во-вторых, если умным русским парням все-таки оказывается нужен русский текст, то они его без труда находят:

1. http://ru.wikipedia.org/wiki/Двоичное_дерево (для общего развития).
2. http://ru.wikipedia.org/wiki/Двоичное_дерево_поиска (оно же binary search tree).
Спасибо сказали: