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

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

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

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

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

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

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

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

Ах да, сортировка должна отрабатывать 300мс на двуядерном процессоре. Т.е можно грубо скинуть алгоритм до 600мс на одном ядре.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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++
Есть программа которая считает расстояние скоростного пути.. и если машина находится близко к впереди идущей машине, то программа нам об...

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

Заполнить диагональ трехмерного массива - C++
#include <iostream> using namespace std; class Arrtridimensional {//Объявили класс public: static const int x = 5, y = 5, z = 5; ...

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

Кстати, а разве можно в куче/стеке задать более 1 миллиона элементов в массиве? Или я чего не помню?
0
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 с.
1
KeyGen
384 / 291 / 6
Регистрация: 07.08.2011
Сообщений: 790
Записей в блоге: 1
14.08.2012, 17:40 #7
Цитата Сообщение от nexen Посмотреть сообщение
Кстати, а разве можно в куче/стеке задать более 1 миллиона элементов в массиве? Или я чего не помню?
Об ограничениях не вкурсе. Я думаю что эллименты ограничены только памятью...
0
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
14.08.2012, 17:48  [ТС] #8
KeyGen, тоже так думал, что в стеке - ограничение, а в куче - пока физ. память не кончится, но, помнится, через раз ошибку выдавало на n>1000*1000 элементов. Сейчас проверить не могу. Надо будет глянуть ;<

SubTerran, хоть это и не совсем та сортировка, что мне нужна, ибо она у них кубом, а мне нужна алмазом, но суть почти та же, а значит - не уложиться мне в полсекунды ; (
1
14.08.2012, 17:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2012, 17:48
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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