Форум программистов, компьютерный форум CyberForum.ru

Сортировка трехмерного массива - C++

Восстановить пароль Регистрация
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
14.08.2012, 16:47     Сортировка трехмерного массива #1
Не могу понять, как (за приемлемое время - не более 300мс) отсортировать трехмерный массив на 500^3 элементов (куб). Сортировка должна выглядеть так, что, если представить куб в виде алмаза (трехмерного ромба) и разрезать его горизонтальными плосколстями на sqrt(2)*500 частей (длина диагонали), то (если смотреть сверху) получится невозрастающая последовательность. Причем, если на одном "этаже" не все числа одинаковые, то сортировка на это "этаже" происходит уже двумерная (тот же ромб, но уже двумерный, где та же невозрастающая последовательность от одного угла до другого), а если и там на одном из "этажей" все числа не одинаковые, то уже последняя - одномерная сортировка.

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

Быть может эта задача уже решена? Погуглил немного, но ничего стоящего не нашел. Более того, меня гугл даже поправил при запросе "сортировка трехмерного массива" на "сортировка двумерного массива", а значит запрос явно "не знаменит".

Ах да, сортировка должна отрабатывать 300мс на двуядерном процессоре. Т.е можно грубо скинуть алгоритм до 600мс на одном ядре.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KeyGen
 Аватар для KeyGen
333 / 289 / 6
Регистрация: 07.08.2011
Сообщений: 789
Записей в блоге: 1
14.08.2012, 16:53     Сортировка трехмерного массива #2
Алгоритмов сортировки не много. Разницы нет что ты будешь сортировать (двух или трех мерный массив). Посмотри в нете именно алгоритмы сортировки.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
14.08.2012, 17:16  [ТС]     Сортировка трехмерного массива #3
Цитата Сообщение от KeyGen Посмотреть сообщение
Алгоритмов сортировки не много. Разницы нет что ты будешь сортировать (двух или трех мерный массив). Посмотри в нете именно алгоритмы сортировки.
В том то и дело, что простой алгоритм сортировки тут не поможет. Да, если бы у меня было 500^3 элементов в одномерном массиве, то я бы легко уложился по времени, но у меня "этажи", которые дают доп. нагрузку и не относятся к сортировке, как к алгоритму. Мой вопрос можно немного перефразировать : "как можно разделить алмаз на "этажи"?
KeyGen
 Аватар для KeyGen
333 / 289 / 6
Регистрация: 07.08.2011
Сообщений: 789
Записей в блоге: 1
14.08.2012, 17:19     Сортировка трехмерного массива #4
Цитата Сообщение от nexen Посмотреть сообщение
Да, если бы у меня было 500^3 элементов в одномерном массиве,
А что если трехмерный слить в одномерный?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
14.08.2012, 17:29  [ТС]     Сортировка трехмерного массива #5
KeyGen, сам метод слития займет много времени, ведь сливать нужно будет по "этажам", но это лучше, чем ничего. Надо попробовать. Правда его ещё потом обратно доставать из одномерного ;< Нужно как-то с индексами похимичить, чтобы легко проходиться по одномерному, как по трехмерному, тогда и конвертации не нужно будет.

Кстати, а разве можно в куче/стеке задать более 1 миллиона элементов в массиве? Или я чего не помню?
SubTerran
8 / 8 / 0
Регистрация: 13.08.2012
Сообщений: 18
14.08.2012, 17:33     Сортировка трехмерного массива #6
Библиотека: Matrix.h
http://www.stroustrup.com/Programming/Matrix/Matrix.h

Библиотека: MatrixIO.h
http://www.stroustrup.com/Programming/Matrix/MatrixIO.h

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//
// 
// 
//
 
#include<iostream>
#include<fstream>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<list>
#include<vector>
#include<algorithm>
#include<stdexcept>
#include <ctime>
#include "Matrix.h"
#include "MatrixIO.h"
 
using namespace Numeric_lib;
using namespace std;
 
//------------------------------------------------------------------------------
 
inline int randint(int max) { return rand()%max; }
 
//------------------------------------------------------------------------------
 
inline void keep_window_open();
 
//------------------------------------------------------------------------------
 
int main()
    try
{
    int dim1 = 500;
    int dim2 = 500;
    int dim3 = 500;
 
    Matrix<int, 3> mtrx(dim1, dim2, dim3);
 
    for (Index i = 0; i < dim1; ++i)
        for (Index j = 0; j < dim2; ++j)
            for (Index k = 0; k < dim3; ++k)
                mtrx(i, j, k) = randint(100);
 
    clock_t t1 = clock();
    if (t1 == clock_t(-1)) {
        cerr << "sorry, no clock\n";
        exit(1);
    }
 
    sort(&mtrx(0, 0, 0), &mtrx(dim1 - 1, dim2 - 1, dim3 - 1));
 
    clock_t t2 = clock();
    if (t2 == clock_t(-1)) {
        cerr << "sorry, clock overflow\n";
        exit(2);
    }
    cout << "Sort three-dimensional array "
        << double(t2-t1)/CLOCKS_PER_SEC << " seconds"
        << " (measurement granularity: "
        << CLOCKS_PER_SEC << " of a second)\n";
 
    keep_window_open();
    return 0;
}
catch (exception& e)
{
    cerr << e.what() << endl;
    keep_window_open();
    return 1;
}
catch (...)
{
    cerr << "exception \n";
    keep_window_open();
    return 2;
}
 
//------------------------------------------------------------------------------
 
inline void keep_window_open()
{
    cin.clear();
    cout << "Please enter a character to exit\n";
    char ch;
    cin >> ch;
    return;
}
 
//------------------------------------------------------------------------------
Release
4,196 с.
4,212 с.
4,218 с.
KeyGen
 Аватар для KeyGen
333 / 289 / 6
Регистрация: 07.08.2011
Сообщений: 789
Записей в блоге: 1
14.08.2012, 17:40     Сортировка трехмерного массива #7
Цитата Сообщение от nexen Посмотреть сообщение
Кстати, а разве можно в куче/стеке задать более 1 миллиона элементов в массиве? Или я чего не помню?
Об ограничениях не вкурсе. Я думаю что эллименты ограничены только памятью...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2012, 17:48     Сортировка трехмерного массива
Еще ссылки по теме:

C++ Сортировка трехмерного массива
C++ Выделить память для трехмерного массива и изменить индексы начального элемента массива
C++ Ошибка нарушения прав доступа при чтении по адресу, возникающая при инициализации трехмерного массива

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
14.08.2012, 17:48  [ТС]     Сортировка трехмерного массива #8
KeyGen, тоже так думал, что в стеке - ограничение, а в куче - пока физ. память не кончится, но, помнится, через раз ошибку выдавало на n>1000*1000 элементов. Сейчас проверить не могу. Надо будет глянуть ;<

SubTerran, хоть это и не совсем та сортировка, что мне нужна, ибо она у них кубом, а мне нужна алмазом, но суть почти та же, а значит - не уложиться мне в полсекунды ; (
Yandex
Объявления
14.08.2012, 17:48     Сортировка трехмерного массива
Ответ Создать тему
Опции темы

Текущее время: 02:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru