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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

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

14.08.2012, 16:47. Просмотров 817. Ответов 7
Метки нет (Все метки)

Не могу понять, как (за приемлемое время - не более 300мс) отсортировать трехмерный массив на 500^3 элементов (куб). Сортировка должна выглядеть так, что, если представить куб в виде алмаза (трехмерного ромба) и разрезать его горизонтальными плосколстями на sqrt(2)*500 частей (длина диагонали), то (если смотреть сверху) получится невозрастающая последовательность. Причем, если на одном "этаже" не все числа одинаковые, то сортировка на это "этаже" происходит уже двумерная (тот же ромб, но уже двумерный, где та же невозрастающая последовательность от одного угла до другого), а если и там на одном из "этажей" все числа не одинаковые, то уже последняя - одномерная сортировка.

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

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

Ах да, сортировка должна отрабатывать 300мс на двуядерном процессоре. Т.е можно грубо скинуть алгоритм до 600мс на одном ядре.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.08.2012, 16:47     Сортировка трехмерного массива
Посмотрите здесь:

Сортировка трехмерного массива - C++
Выполнить сортировку трехмерного массива методом вставки, пызырька!

Выделить память для трехмерного массива и изменить индексы начального элемента массива - C++
Выделить память для трехмерного массива а. Изменить индексы начального элемента массива на . Протестировать программу

Заполнение трехмерного массива - C++
Есть программа которая считает расстояние скоростного пути.. и если машина находится близко к впереди идущей машине, то программа нам об...

Заполнение трехмерного массива - C++
Помогите с заполнением трехмерного массива, мне нужно чтобы он заполнился по порядку от 0 до 60. #include <stdio.h> #include <malloc.h>...

Сумма элементов трехмерного массива - C++
Имеется трехмерный массив из 3-ех слоев по 3Х3 элемента в каждом слое, в первом слое все элементы единицы, во втором слое - двойки, в...

Ручное заполнение трехмерного массива - C++
Доброго времени суток. Пишу лексический анализатор , и в базе данных стандартных типов анализатора (заголовочный файл) мне нужно объявить...

Заполнить срез трехмерного массива - C++
Добрый день. Нужно заполнить срез 3д матрицы (см. вложения, там есть картинка). Все подготовительные этапы по вводу самого массива и...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
KeyGen
383 / 290 / 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
383 / 290 / 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
383 / 290 / 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++
#include &lt;iostream&gt; using namespace std; class Arrtridimensional {//Объявили класс public: static const int x = 5, y = 5, z = 5; ...

Считывание из файла трехмерного массива и запись - C++
Доброго времени суток, прошу помочь в следующем. :) Собственно вот создание трехмерного массива int c = 2; int a = 3; int b = 2;...

Создать двумерный массив из трехмерного массива по условию - C++
Дан трехмерный массив, создать двумерный массив, столбцами которого будут случайные столбцы(в вышину) первого массива. Задачу решить с...

Заполнение трехмерного динамического массива типа Char - C++
вот само задание : Создать набор функций, позволяющих работать со школьным расписанием. Предположим, что школьник учится 5 дней в неделю...

Посчитать среднегеометрическое главной диагонали трехмерного массива (NxNxN) - 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     Сортировка трехмерного массива
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru