Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
1

Эффективный алгоритм сортировки одного массива по данным другого массива

16.11.2018, 19:31. Просмотров 782. Ответов 27
Метки нет (Все метки)

Всем привет!
Время сортировки массива с 2 млн. строк - 0,85 сек.,
Время сортировки массива индексов по данным этого же массива строк - 1,12 сек.
Итого разница в 30%
Можно ли оптимизировать приложенный алгоритм сортировки массива с индексами по данным другого массива со строками?
Существует ли другой, более эффективный, алгоритм сортировки массива с индексами по данным другого массива?

Ограничений по памяти нет, цель - скорость.

Пример:
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
#include "stdafx.h"
#include <vector>
#include <thread>
#include <algorithm>
#include <numeric>
#include <string>
#include <iostream>
 
bool comparestring(wchar_t* lhs, wchar_t* rhs) {
    if (lhs == NULL) return false;
    if (rhs == NULL) return true;
    return wcscmp(lhs, rhs) < 0;
}
 
int main()
{
    std::vector<wchar_t*> vwchar (2000000);
    for (long i = 1; i < vwchar.size(); i++) vwchar[i] = new wchar_t;
 
    for (long i = 1; i < vwchar.size(); i++) wcscpy(vwchar[i],std::to_wstring(rand() | (rand() << 8)).c_str()); //Заполняем массив строк - Целое число в интервале [0; 2^(15+8))
    std::vector<wchar_t*> vwchar2(vwchar); //делаем копию массива для второго блока расчетов
    
    ///первый блок расчетов для сравнения скорости сортировки самого массива и массива индексов ниже.
    unsigned int start_time = clock(); // начальное время
    std::sort(vwchar.begin(), vwchar.end(), comparestring); //сортируем
    unsigned int end_time = clock(); // конечное время
 
    unsigned int search_time = end_time - start_time; // искомое время
    wprintf(L"Time, sec: %f (size - %zi,  first - %Ls, last - %Ls) \n", search_time / 1000.0, vwchar.size(), vwchar[0], vwchar[vwchar.size() - 1]);
    
    ////второй блок расчетов - вопрос по этому блоку
    std::vector<long> vlong(vwchar.size());
    std::iota(std::begin(vlong), std::end(vlong), 0); //заполняем массив индексов
 
    unsigned int start_time2 = clock(); // начальное время
    std::sort(vlong.begin(), vlong.end(), [&vwchar2](long a, long b) { return comparestring(vwchar2[a], vwchar2[b]); }); //сортируем массив индексов по данным массива строк
    unsigned int end_time2 = clock(); // конечное время
    
    unsigned int search_time2 = end_time2 - start_time2; // искомое время
    wprintf(L"Time, sec: %f (size - %zi, first - %lu, last - %lu) \n", search_time2 / 1000.0, vlong.size(), vlong[0], vlong[vwchar.size() - 1]);
 
    _wsystem(L"pause");
    return 0;
}
Благодарю.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.11.2018, 19:31
Ответы с готовыми решениями:

Подскажите эффективный алгоритм сортировки массива (желательно многомерного ) на VB
Подскажите эффективный алгоритм сортировки массива (желательно многомерного ) на VB

Эффективный алгоритм перетасовки элементов массива
Друзья, написал вот такую функцию public static void arrayShuffle(int arr) { ...

Выбора из массива по данным другого массива
Помогите пожалуста с проблемкой ) Не очень сильна в массивах. Из базы выбраны данные,...

Разработать эффективный алгоритм быстрой сортировки
Быстрая сортировка. Разработайте эффективный алгоритм для упорядочивания n элементов таким образом,...

27
164 / 107 / 57
Регистрация: 30.08.2018
Сообщений: 357
Завершенные тесты: 1
17.11.2018, 00:15 2
Ошибок многовато, вы наверно на с++ редко пишите
Первый элемент массива пропустили. Нумерация массива с нуля.
Цитата Сообщение от bedvit Посмотреть сообщение
for (long i = 1; i < vwchar.size(); i++)
Массив строк ? А вас только один wchar_t, один символ
Цитата Сообщение от bedvit Посмотреть сообщение
vwchar[i] = new wchar_t;
и в него пытаетесь копировать строку
Цитата Сообщение от bedvit Посмотреть сообщение
wcscpy(vwchar[i],std::to_wstring
Цитата Сообщение от bedvit Посмотреть сообщение
Заполняем массив строк - Целое число в интервале [0; 2^(15+8))
Цитата Сообщение от bedvit Посмотреть сообщение
rand() | (rand() << 8)
это что-то не то

2^(15+8) это
C++
1
 2 << ((15+8) - 1)
Целое число в интервале [0; 2^(15+8))
C++
1
int val = rand() % (2 << ((15+8) - 1));
Добавлено через 1 минуту
Цитата Сообщение от bedvit Посмотреть сообщение
Можно ли оптимизировать
А дальше уже и не смотрел.
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
Завершенные тесты: 6
17.11.2018, 03:20 3
Там не прямо большая разница выходит, если нормально писать:
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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <ctime>
 
int main()
{
    using namespace std;
    vector<wstring> vwchar(2000000);
    for (wstring& s : vwchar)
        s = to_wstring(rand() * 1LL << 16 + rand());
 
    // это работает за 1634 мс
    vector<wstring> buff(vwchar);
    cout << "Simple sort ";
    unsigned int start_time = clock(); // начальное время
    sort(buff.begin(), buff.end());
    unsigned int end_time = clock();
    cout << end_time - start_time << endl;
 
    // Попытался придумать умный алгоритм, не получилось.
    // Работает 3391 мс
    vector<size_t> sorted_indexes(vwchar.size());
    cout << "Index sort ";
    start_time = clock();
    typedef map<wstring, vector<size_t>> indexing_type;
    indexing_type sorting;
    for (size_t i = 0, size = vwchar.size(); i < size; ++i)
        sorting[vwchar[i]].push_back(i);
    size_t* data_pointer = sorted_indexes.data();
    for(const indexing_type::value_type& p:sorting)
    {
        memcpy(data_pointer, p.second.data(), p.second.size() * sizeof(size_t));
        data_pointer += p.second.size();
    }
    end_time = clock();
    cout << end_time - start_time << endl;
 
    // Это работает за 1990 мс
    cout << "Lambda index sort ";
    vector<size_t> sorted_indexes2(vwchar.size());
    start_time = clock();
    for (size_t i = 0; i < sorted_indexes2.size(); ++i)
        sorted_indexes2[i] = i;
    std::sort(sorted_indexes2.begin(), sorted_indexes2.end(), [&vwchar](size_t l, size_t r)
    {
        return vwchar[l] < vwchar[r];
    });
    end_time = clock();
    cout << end_time - start_time << endl;
 
}
Добавлено через 7 минут
Вообще, думаю, основное падение производительности из-за кэш-промахов, с этим ничего не поделать.
0
3143 / 2616 / 697
Регистрация: 25.03.2012
Сообщений: 9,415
Записей в блоге: 1
Завершенные тесты: 1
17.11.2018, 03:22 4
Цитата Сообщение от bedvit Посмотреть сообщение
C++
1
2
3
4
5
for (long i = 1; i < vwchar.size(); i++)
 vwchar[i] = new wchar_t; 
for (long i = 1; i < vwchar.size(); i++)
 wcscpy(vwchar[i],std::to_wstring(rand() | (rand() << 8)).c_str());
 //Заполняем массив строк - Целое число в интервале [0; 2^(15+8))
а что, так можно было?
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
Завершенные тесты: 6
17.11.2018, 04:01 5
Я соврал
Исправил проблему с кэш-промахами. Стало на 0,3 секунды быстрее и медленнее простой сортировки всего на 143 мс.
Кликните здесь для просмотра всего текста
Simple sort 1687
Index sort 3531
Lambda index sort 2102
Pair sort 1830
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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <ctime>
 
int main()
{
    using namespace std;
    vector<wstring> vwchar(2000000);
    for (wstring& s : vwchar)
        s = to_wstring(rand() * 1LL << 16 + rand());
 
    cout << "Simple sort ";
    vector<wstring> buff(vwchar);
    unsigned int start_time = clock(); // начальное время
    sort(buff.begin(), buff.end());
    unsigned int end_time = clock();
    cout << end_time - start_time << endl;
 
    // Попытался придумать умный алгоритм, не получилось.
    cout << "Index sort ";
    vector<size_t> sorted_indexes(vwchar.size());
    start_time = clock();
    typedef map<wstring, vector<size_t>> indexing_type;
    indexing_type sorting;
    for (size_t i = 0, size = vwchar.size(); i < size; ++i)
        sorting[vwchar[i]].push_back(i);
    size_t* data_pointer = sorted_indexes.data();
    for (const indexing_type::value_type& p : sorting)
    {
        memcpy(data_pointer, p.second.data(), p.second.size() * sizeof(size_t));
        data_pointer += p.second.size();
    }
    end_time = clock();
    cout << end_time - start_time << endl;
 
 
    cout << "Lambda index sort ";
    start_time = clock();
    vector<size_t> sorted_indexes2(vwchar.size());
    for (size_t i = 0; i < sorted_indexes2.size(); ++i)
        sorted_indexes2[i] = i;
    std::sort(sorted_indexes2.begin(), sorted_indexes2.end(), [&vwchar](size_t l, size_t r)
    {
        return vwchar[l] < vwchar[r];
    });
    end_time = clock();
    cout << end_time - start_time << endl;
 
    vector<pair<size_t, wstring>> pair_copy(vwchar.size());
    cout << "Pair sort ";
    start_time = clock();
    for (size_t i = 0; i < sorted_indexes2.size(); ++i)
        pair_copy[i] = make_pair(i, vwchar[i]);
    std::sort(pair_copy.begin(), pair_copy.end(),
              [](const pair<size_t, wstring>& l, pair<size_t, wstring>& r)
              {
                return l.second < r.second;
              });
    end_time = clock();
    cout << end_time - start_time << endl;
 
}


Добавлено через 19 минут
Снова соврал: забыл перенести выделение памяти под время. Правда, почти ничего не поменялось.
Simple sort 1625
Index sort 3318
Lambda index sort 1987
Pair sort 1764
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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <ctime>
 
int main()
{
    using namespace std;
    vector<wstring> vwchar(2000000);
    for (wstring& s : vwchar)
        s = to_wstring(rand() * 1LL << 16 + rand());
 
    cout << "Simple sort ";
    vector<wstring> buff(vwchar);
    unsigned int start_time = clock(); // начальное время
    sort(buff.begin(), buff.end());
    unsigned int end_time = clock();
    cout << end_time - start_time << endl;
 
    // Попытался придумать умный алгоритм, не получилось.
    cout << "Index sort ";
    vector<size_t> sorted_indexes(vwchar.size());
    start_time = clock();
    typedef map<wstring, vector<size_t>> indexing_type;
    indexing_type sorting;
    for (size_t i = 0, size = vwchar.size(); i < size; ++i)
        sorting[vwchar[i]].push_back(i);
    size_t* data_pointer = sorted_indexes.data();
    for (const indexing_type::value_type& p : sorting)
    {
        memcpy(data_pointer, p.second.data(), p.second.size() * sizeof(size_t));
        data_pointer += p.second.size();
    }
    end_time = clock();
    cout << end_time - start_time << endl;
 
 
    cout << "Lambda index sort ";
    start_time = clock();
    vector<size_t> sorted_indexes2(vwchar.size());
    for (size_t i = 0; i < sorted_indexes2.size(); ++i)
        sorted_indexes2[i] = i;
    std::sort(sorted_indexes2.begin(), sorted_indexes2.end(), [&vwchar](size_t l, size_t r)
    {
        return vwchar[l] < vwchar[r];
    });
    end_time = clock();
    cout << end_time - start_time << endl;
 
 
    cout << "Pair sort ";
    start_time = clock();
    vector<pair<size_t, wstring>> pair_copy(vwchar.size());
    for (size_t i = 0; i < sorted_indexes2.size(); ++i)
        pair_copy[i] = make_pair(i, vwchar[i]);
    std::sort(pair_copy.begin(), pair_copy.end(),
              [](const pair<size_t, wstring>& l, pair<size_t, wstring>& r)
              {
                return l.second < r.second;
              });
    end_time = clock();
    cout << end_time - start_time << endl;
 
}
Добавлено через 13 минут
Поясняю, как это работает: при сортировке обычной у нас в кэше процессора находятся данные объектов строк и адрес внутренного массива этих строк (или указателя и их данных, если писать по сишному) — 1 локальная и 1 не особо локальная область памяти.

Когда мы сортируем массив индексов, в кэш надо пихнуть индексы, объекты строк, и данные самих строк. В итоге лезет меньше, да и расстояние между блоками индексов и строк далёкое. В итоге время тратится на подгрузку данных из ОЗУ в кэш (кэш-промахи).

Когда мы объединяем индекс и строку в один объект — пару, мы локализуем индексы и объекты строк в одном месте, поэтому кэш промахов становится меньше.

Вы можете дальше попробовать уменьшить время, использовав вот эту структуру вместо строк и пары, например, но судя по коду из Вашего примера, Вам стоит просто взять то, что я уже постил.
Размер этой структуры будет 12 байт на x64, что может улучшить кэширование, но подозреваю, что выигрыш будет минимальным.
Ну, и плюс экономия на capacity и size у строки.
C++
1
2
3
4
5
6
7
#pragma pack(push, 1)
struct index_and_string
{
    uint32_t index; // Вам хватит на 2 млн.
    wchar* string_ptr;
}
#pragma pack(pop)
1
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
17.11.2018, 10:03  [ТС] 6
Цитата Сообщение от JaponDemon Посмотреть сообщение
Ошибок многовато, вы наверно на с++ редко пишите
Да это не мой профиль. По ошибкам:
Цитата Сообщение от JaponDemon Посмотреть сообщение
Первый элемент массива пропустили. Нумерация массива с нуля.
- так и было задумано, во входящем массиве могут быть не инициализированные данные, т.е.NULL, собственно для этого и сomparestring(wchar_t* lhs, wchar_t* rhs).
Цитата Сообщение от JaponDemon Посмотреть сообщение
Массив строк ? А вас только один wchar_t, один символ
- это вектор, смотрите внимательнее.
Цитата Сообщение от JaponDemon Посмотреть сообщение
и в него пытаетесь копировать строку
- это вектор, смотрите внимательнее.
Цитата Сообщение от JaponDemon Посмотреть сообщение
это что-то не то
- докажите. Мин, Макс показывают, что генерируются числа в этом диапазоне, да и логика понятна (перекрываются два rand, один сдвинут на 8 разрядов двойки, то что пересечение (перекрытие двух rand) более плотное, для теста - не имеет значения). В реале вектор строк - внешний, я его не создаю.
Цитата Сообщение от JaponDemon Посмотреть сообщение
А дальше уже и не смотрел.
может оно и к лучшему.

New man, спасибо за код, не могу сейчас проверить, как дойду до ПК, отпишусь. Учитываются ли в нем, что во входящем массиве могут быть не инициализированные данные, см. bool comparestring.
Kuzia domovenok, для примера зашло, в основном коде массив входящий, этого блока все равно не будет

Добавлено через 15 минут
Цитата Сообщение от bedvit Посмотреть сообщение
перекрываются два rand, один сдвинут на 8 разрядов двойки, то что пересечение (перекрытие двух rand) более плотное, для теста - не имеет значения
В итоге диапазон не с нуля, а с 2^8. Закомментированный текст в коде не поправил (здесь мой промах). Но для теста это не имеет значения. Задача этой строки получить два миллиона разных чисел/строк.
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
Завершенные тесты: 6
17.11.2018, 14:06 7
bedvit,
- это вектор, смотрите внимательнее.
Вы не поняли. Вы в элементе вектора храните указатель на один символ, а потом пытаетесь туда копировать строку.
0
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
17.11.2018, 14:41  [ТС] 8
Цитата Сообщение от New man Посмотреть сообщение
Вы в элементе вектора храните указатель на один символ, а потом пытаетесь туда копировать строку
New man, для теста этот вариант проходит, какая разница указатель на один элемент или на несколько, насколько я понимаю указатель на массив в Си - это указатель на первый элемент массива (этого не будет в рабочем варианте). Такое ощущение, что тест никто мой не запускал. New man, к сожалению у меня входящий массив <wchar_t*>, а у вас решение на wstring. Причем в массиве могут быть не инициализированые переменные (в тексте я этого не упомянул, но в примере этот массив даётся, поэтому он и начинается с 1, а не с 0).
0
3143 / 2616 / 697
Регистрация: 25.03.2012
Сообщений: 9,415
Записей в блоге: 1
Завершенные тесты: 1
17.11.2018, 14:49 9
я понять не могу, кто тут у кого помощи просит. Вам указывают на ошибки - вы отвечаете в стиле "для теста можно принять, что чёрное это белое. Какая разница, чёрное это или белое, если в Сив цветовой палитре чёрное это цвет, который окрашен в белый?"
Я сейчас вижу как вы учите Newman, что массивы в Си это то же самое, что указатели - абсурдно!

Добавлено через 3 минуты
Предлагаю приостановить оффтоп на том, что вы согласитесь, что массив это не указатель и сделаете исправления соответствующие.
0
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
17.11.2018, 15:03  [ТС] 10
Не имею привычку кого-то учить по теме, которая не относится к моему профилю. И не в коем случае, не делаю это сейчас. Я лишь упомянул, что как создан тестовый массив для основного вопроса, не является существенным. Потому как тема топика про другое и тестовый массив отрабатывает как нужно. Если это не так укажите, где всплывёт эта ошибка? За указание неточности в формировании тестового массива благодарю. Конструктивную критику приветствую. По основному вопросу есть какие либо комментарии? Отсортировать массив индексов по входящему массиву <wchar_t*> (элементы могут быть NULL), не медленнее (или приближаясь), чем сортировка самого массива строк.

Добавлено через 45 секунд
Готов поправится, тем более это верное замечание.
0
164 / 107 / 57
Регистрация: 30.08.2018
Сообщений: 357
Завершенные тесты: 1
17.11.2018, 15:12 11
Цитата Сообщение от bedvit Посмотреть сообщение
- докажите. Мин, Макс показывают, что генерируются числа в этом диапазоне, да и логика понятна
bedvit
вот же https://www.ideone.com/NmZ11s,
это никак не число в интервале [0; 2^(15+8)) :

C++
1
2
3
4
5
6
7
8
9
int main()
{
    srand(static_cast<unsigned int>(time(nullptr)));
    
    for (int i = 0; i < 10; ++i)
    {
        std::cout << (rand() | (rand() << 8)) << std::endl;
    }
}
1063608218
-1481638357
-135594279
-1094781152
-159401002
-556729653
-536891478
2130698111
1441595097
681536578
0
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
17.11.2018, 15:50  [ТС] 12
JaponDemon, да, я отметил что комментарий к этому коду был неверный. Но он (код) полностью удовлетворяет тестовому массиву. По большему счету, вообще без разницы, что там будет, главное 2 млн. разных значений.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "stdafx.h"
#include <vector>
#include <thread>
#include <algorithm>
 
    int main()
    {
        std::vector<long> myVector(20000000);
        
        for (long x = 0; x < 20000000; x++) 
        {
            myVector[x] = rand()| (rand() << 8); 
        }
        std::sort(myVector.begin(), myVector.end());
        wprintf(L"size: %zu, min - %lu, max - %lu \n", myVector.size(), myVector[0], myVector[myVector.size()-1]);
        system("pause");
        return 0;
    }
На 20 млн. итераций, следующие рамки:
size: 20000000, min - 202, max - 8388607
0
164 / 107 / 57
Регистрация: 30.08.2018
Сообщений: 357
Завершенные тесты: 1
17.11.2018, 15:56 13
Цитата Сообщение от bedvit Посмотреть сообщение
да, я отметил что комментарий к этому коду был неверный.
Да, хорошо понял
Вы просили
Цитата Сообщение от bedvit Посмотреть сообщение
- докажите.
поэтому ответил
0
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
17.11.2018, 18:17  [ТС] 14
JaponDemon,
поэтому ответил
принял.
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
Завершенные тесты: 6
18.11.2018, 00:56 15
Цитата Сообщение от bedvit Посмотреть сообщение
какая разница указатель на один элемент или на несколько, насколько я понимаю указатель на массив в Си - это указатель на первый элемент массива (этого не будет в рабочем варианте).
Массив — это непрерывная область памяти, заполненная элементами одного типа. А указатель может указывать на один элемент или на массив.
Мы же выделили 2 байта (если не ошибаюсь), и пытаетесь туда скопировать n*2 байт. Какой-нибудь GCC в ответ на это начал бы просто игнорировать копирование, например, так как это Undefined Behaviour.


А так, держите, что хотели. Утечки памяти на Ваш страх и риск. Сортирует у меня примерно секунду в режиме x64 и 260 мс в режиме x86.
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
struct str_index
{
    size_t index;
    const wchar_t* wstr;
    friend bool operator<(const str_index& l, const str_index& r);
    friend bool operator==(const str_index& l, const str_index& r);
    friend bool operator!=(const str_index& l, const str_index& r) { return !(l == r); }
    friend bool operator>(const str_index& l, const str_index& r);
};
 
bool operator<(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return r.wstr != nullptr;
    if (r.wstr == nullptr) return false;
    return wcscmp(l.wstr, r.wstr) < 0;
}
 
bool operator==(const str_index& l, const str_index& r)
{
    return l.wstr == r.wstr ||
        l.wstr != nullptr && r.wstr != nullptr && wcscmp(l.wstr, r.wstr) == 0;
}
 
bool operator>(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return false;
    if (r.wstr == nullptr) return true;
    return wcscmp(l.wstr, r.wstr) > 0;
}
 
...
 
    cout << "Pointer sort ";
    start_time = clock();
    vector<str_index> pair_ptrs(vwchar.size());
    for (uint32_t i = 0; i < vwchar.size(); ++i)
        pair_ptrs[i] = str_index{i, vwchar[i].c_str()};
    std::sort(pair_ptrs.begin(), pair_ptrs.end());
    end_time = clock();
    cout << end_time - start_time << endl;
1
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
19.11.2018, 18:28  [ТС] 16
Цитата Сообщение от New man Посмотреть сообщение
Мы же выделили 2 байта (если не ошибаюсь), и пытаетесь туда скопировать n*2 байт.
Да это верно. Выделил память - строка 54. Опять же здесь момент неопределенный, если std::vector<wchar_t*> это массив ссылок, то возможно массив самих строк (wchar_t*) может хранится не последовательно, а как-то блоками? Пока не пойму, правильный ли это механизм заполнения динамического массива сишных строк (через вектор). Что-то делаю не верно, потому как на х64 отрабатывает норм, на х32 - крашится на выделении памяти "new wchar_t". Подозрения, что в векторе должен быть непрерывный блок памяти, и не хватает памяти под выделение нового блока, для новой строки.

Протестировал 4 варианта:
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include "stdafx.h"
#include <vector>
#include <thread>
#include <algorithm>
#include <numeric>
#include <string>
#include <iostream>
 
//Lambda index sort - №2
bool comparestring(wchar_t* lhs, wchar_t* rhs) {
    if (lhs == NULL) return false;
    if (rhs == NULL) return true;
    return wcscmp(lhs, rhs) < 0;
}
//
 
//Pointer sort  - №4
struct str_index
{
    size_t index;
    const wchar_t* wstr;
    friend bool operator<(const str_index& l, const str_index& r);
    friend bool operator==(const str_index& l, const str_index& r);
    friend bool operator!=(const str_index& l, const str_index& r) { return !(l == r); }
    friend bool operator>(const str_index& l, const str_index& r);
};
 
bool operator<(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return r.wstr != nullptr;
    if (r.wstr == nullptr) return false;
    return wcscmp(l.wstr, r.wstr) < 0;
}
 
bool operator==(const str_index& l, const str_index& r)
{
    return l.wstr == r.wstr ||
        l.wstr != nullptr && r.wstr != nullptr && wcscmp(l.wstr, r.wstr) == 0;
}
 
bool operator>(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return false;
    if (r.wstr == nullptr) return true;
    return wcscmp(l.wstr, r.wstr) > 0;
}
 
 
int main()
{
    std::vector<wchar_t*> vwchar(2000000);
    for (long i = 5; i < vwchar.size(); i++) {
        std::wstring wstTmp = std::to_wstring(rand() % (2 << ((15 + 8) - 1))); //строка/целое число в интервале [0; 2^(15+8))
        vwchar[i] = new wchar_t(wcslen(wstTmp.c_str()) + 1);//выделим необходимую память
        wcscpy(vwchar[i], wstTmp.c_str()); //Заполняем массив строк
    }
    std::vector<wchar_t*> vwchar2(vwchar); //делаем копию массива для Lambda index sort, Pair sort,Pointer sort
 
    //Simple sort - №1
    unsigned int start_time = clock(); // начальное время
    std::sort(vwchar.begin(), vwchar.end(), comparestring); //сортируем
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    wprintf(L"Simple sort - 1, sec: %f (size - %zi,  first - %Ls, last - %Ls) \n", search_time / 1000.0, vwchar.size(), vwchar[0], vwchar[vwchar.size() - 1]);
 
    //Lambda index sort - №2
    std::vector<long> vlong(vwchar2.size());
    std::iota(std::begin(vlong), std::end(vlong), 0); //заполняем массив индексов
    unsigned int start_time2 = clock(); // начальное время
    std::sort(vlong.begin(), vlong.end(), [&vwchar2](long a, long b) { return comparestring(vwchar2[a], vwchar2[b]); }); //сортируем массив индексов по данным массива строк
    unsigned int end_time2 = clock(); // конечное время
    unsigned int search_time2 = end_time2 - start_time2; // искомое время
    wprintf(L"Lambda index sort - 2, sec: %f (size - %zi, first - %lu, last - %lu) \n", search_time2 / 1000.0, vlong.size(), vlong[0], vlong[vwchar.size() - 1]);
 
    //Pair sort  - №3
    std::vector<size_t> sorted_indexes3(vwchar2.size());
    for (size_t i = 0; i < sorted_indexes3.size(); ++i) sorted_indexes3[i] = i;
    unsigned int start_time3 = clock(); // начальное время
    std::vector<std::wstring> vwchar3(vwchar2.size()); //перекладываем wchar_t* в std::wstring
    for (int i = 5; i < vwchar2.size(); i++) {
        std::wstring wstr3(vwchar2[i]);
        vwchar3[i] = wstr3;
    }
    std::vector<std::pair<size_t, std::wstring>> pair_copy3(vwchar3.size());
    for (size_t i = 0; i < sorted_indexes3.size(); ++i) pair_copy3[i] = std::make_pair(i, vwchar3[i]);
    std::sort(pair_copy3.begin(), pair_copy3.end(),
        [](const std::pair<size_t, std::wstring>& l, std::pair<size_t, std::wstring>& r)
    {
        return l.second < r.second;
    });
    std::vector<long> vlong3(vwchar2.size());
    for (int i = 0; i < pair_copy3.size(); i++) vlong3[i] = pair_copy3[i].first; //переклыдываем pair в массив индексов 
    unsigned int end_time3 = clock(); // конечное время
    wprintf(L"Pair sort - 3, sec: %f  \n", (end_time3 - start_time3) / 1000.0);
 
    //Pointer sort  - №4
    unsigned int start_time4 = clock();
    std::vector<std::wstring> vwchar4(vwchar2.size());//перекладываем wchar_t* в std::wstring
    for (int i = 5; i < vwchar2.size(); i++) {
        std::wstring wstr4(vwchar2[i]);
        vwchar4[i] = wstr4; 
    }
    std::vector<str_index> pair_ptrs4(vwchar2.size());
 
    for (uint32_t i = 5; i < vwchar2.size(); ++i) 
        pair_ptrs4[i] = str_index{ i, vwchar4[i].c_str() };
    std::sort(pair_ptrs4.begin(), pair_ptrs4.end());
    std::vector<long> vlong4(vwchar2.size());
    for (int i = 0; i < pair_ptrs4.size(); i++) vlong4[i] = pair_ptrs4[i].index; //переклыдываем pair в массив индексов 
    unsigned int end_time4 = clock();
    wprintf(L"Pointer sort - 4, sec: %f  \n", (end_time4 - start_time4) / 1000.0);
    
    _wsystem(L"pause");
    return 0;
}
х64
Simple sort - 1, sec: 0.728000
Lambda index sort - 2, sec: 0.926000
Pair sort - 3, sec: 0.446000
Pointer sort - 4, sec: 0.688000

х32
Simple sort - 1, sec: 0.767000
Lambda index sort - 2, sec: 0.960000
Pair sort - 3, sec: 0.548000
Pointer sort - 4, sec: 0.643000

Цитата Сообщение от New man Посмотреть сообщение
Сортирует у меня примерно секунду в режиме x64 и 260 мс в режиме x86.
На х32 в 4 раза быстрее? у меня нет почти одинаковое время (см. выше).
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
Завершенные тесты: 6
19.11.2018, 19:47 17
Цитата Сообщение от bedvit Посмотреть сообщение
std::vector<wchar_t*> это массив ссылок
Это динамический массив указателей. Ссылки и указатели в C++ — разные вещи, хотя в глубине сводятся к одному и тому же.

Валидный метод скопировать wstring в сишную строку:
C++
1
2
3
4
5
6
7
// s — std::wstring
wchar_t* pointer = new wchar_t[s.size() + 1]; // Выделили массив в куче под символы и окончательный nullptr
memcpy(pointer, s.c_str(), s.size()+1); // Скопировали символы в новое место
///...
/// Работаем со строками
///...
delete[] pointer; // удаляем память в куче.
В случае массива строк, Вам надо выделять память в куче под каждый элемент подобным образом и так же удалять каждый элемент.

Цитата Сообщение от bedvit Посмотреть сообщение
у меня нет почти одинаковое время (см. выше).
Потому что Вы написали какую-то ерунду, а не то, что я писал. И измеряете Вы не сортировку, а лишние копирования данных.
Зачем Вы пихнули вот это в измеряемое время?
C++
1
2
3
4
5
    std::vector<std::wstring> vwchar4(vwchar2.size());//перекладываем wchar_t* в std::wstring
    for (int i = 5; i < vwchar2.size(); i++) {
        std::wstring wstr4(vwchar2[i]);
        vwchar4[i] = wstr4; 
    }
Вы 2 МИЛЛИОНА раз создали строки в векторе, затем сделали: 2 миллиона копирований в wstr4, 2 миллиона копирований из wstr4 в vwchar4[i], 2 миллиона удалений wstr4. Итого Вы выделили без никакой нужды выделили память в размере 2 раза большем, чем исходные данные, затем удалили половину и лишь затем начали собственно то, что я предлагал. Естественно всё будет выполняться одинаково, ведь сортировки тут совсем не самая медленная часть.

Добавлено через 1 минуту
В моём алгоритме ровно одно выделение памяти: в вектор из str_index.
Зачем Вы копируете то, что не изменяется?

Добавлено через 2 минуты
Вам стоит почитать, что Вам предлагают.
У Вас на входе указатели на cишные строки, в моей структуре есть индекс и указатель на сишную строку, ЗАЧЕМ нужно создавать ненужные wstring?

Добавлено через 5 минут
ПИСАТЬ НАДО ВОТ ТАК
C++
1
2
3
4
5
6
7
8
9
10
std::vector<size_t> sorted_indexes(const std::vector<wchar_t*> strings)
{
    std::vector<str_index> pairs(strings.size());
    for (size_t i = 5; i < strings.size(); ++i) 
        pairs[i] = str_index{ i, strings[i] };
    std::sort(pairs.begin(), pairs.end());
    std::vector<size_t> out(pairs.size());
    std::transform(pairs.begin(), pairs.end(), out.begin(), [](const str_index& i){return i.index;});
    return out;
}
Добавлено через 2 минуты
Цитата Сообщение от bedvit Посмотреть сообщение
new wchar_t(wcslen(wstTmp.c_str()) + 1)
И да, так выделять под строку память неправильно.
Массив всегда выделяется на куче с помощью квадратных скобок, Вы же выделили место под один символ, в который записали символ с кодом wcslen(wstTmp.c_str())+1.
1
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
19.11.2018, 21:08  [ТС] 18
Цитата Сообщение от New man Посмотреть сообщение
Это динамический массив указателей.
Имел ввиду именно это, написал не верно.
Цитата Сообщение от New man Посмотреть сообщение
В случае массива строк, Вам надо выделять память в куче под каждый элемент подобным образом и так же удалять каждый элемент.
так и делаю, только через wcscpy
Цитата Сообщение от New man Посмотреть сообщение
Зачем Вы пихнули вот это в измеряемое время?
Потому, что мне что бы работать с std::wstring к примеру строка 37 в вашем коде
C++
1
pair_ptrs[i] = str_index{i, vwchar[i].c_str()};
, мне их нужно создать из wchar_t*, а это время.
Цитата Сообщение от New man Посмотреть сообщение
У Вас на входе указатели на cишные строки, в моей структуре есть индекс и указатель на сишную строку, ЗАЧЕМ нужно создавать ненужные wstring?
Был код через std::wstring, менять не стал, но замечание правильное, поправил.
Цитата Сообщение от New man Посмотреть сообщение
выделяется на куче с помощью квадратных скобок
пропустил... благодарю.
Добавил новый метод - 3.1 и оставил старый 3.2
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include "stdafx.h"
#include <vector>
#include <thread>
#include <algorithm>
#include <numeric>
#include <string>
#include <iostream>
 
//Lambda index sort - №2
bool comparestring(wchar_t* lhs, wchar_t* rhs) {
    if (lhs == NULL) return false;
    if (rhs == NULL) return true;
    return wcscmp(lhs, rhs) < 0;
}
 
//Pointer sort  - №4
struct str_index
{
    size_t index;
    const wchar_t* wstr;
    friend bool operator<(const str_index& l, const str_index& r);
    friend bool operator==(const str_index& l, const str_index& r);
    friend bool operator!=(const str_index& l, const str_index& r) { return !(l == r); }
    friend bool operator>(const str_index& l, const str_index& r);
};
 
bool operator<(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return r.wstr != nullptr;
    if (r.wstr == nullptr) return false;
    return wcscmp(l.wstr, r.wstr) < 0;
}
 
bool operator==(const str_index& l, const str_index& r)
{
    return l.wstr == r.wstr ||
        l.wstr != nullptr && r.wstr != nullptr && wcscmp(l.wstr, r.wstr) == 0;
}
 
bool operator>(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return false;
    if (r.wstr == nullptr) return true;
    return wcscmp(l.wstr, r.wstr) > 0;
}
 
int main()
{
    std::vector<wchar_t*> vwchar(2000000);
    for (long i = 5; i < vwchar.size(); i++) {
        std::wstring wstTmp = std::to_wstring(rand() % (2 << ((15 + 8) - 1))); //строка/целое число в интервале [0; 2^(15+8))
        vwchar[i] = new wchar_t[wcslen(wstTmp.c_str()) + 1];//выделим необходимую память
        wcscpy(vwchar[i], wstTmp.c_str()); //Заполняем массив строк
    }
    std::vector<wchar_t*> vwchar2(vwchar); //делаем копию массива для Lambda index sort, Pair sort,Pointer sort
 
    //Simple sort - №1
    unsigned int start_time = clock(); // начальное время
    std::sort(vwchar.begin(), vwchar.end(), comparestring); //сортируем
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    wprintf(L"Simple sort - 1, sec: %f (size - %zi,  first - %Ls, last - %Ls) \n", search_time / 1000.0, vwchar.size(), vwchar[0], vwchar[vwchar.size() - 1]);
 
    //Lambda index sort - №2
    std::vector<long> vlong(vwchar2.size());
    std::iota(std::begin(vlong), std::end(vlong), 0); //заполняем массив индексов
    unsigned int start_time2 = clock(); // начальное время
    std::sort(vlong.begin(), vlong.end(), [&vwchar2](long a, long b) { return comparestring(vwchar2[a], vwchar2[b]); }); //сортируем массив индексов по данным массива строк
    unsigned int end_time2 = clock(); // конечное время
    unsigned int search_time2 = end_time2 - start_time2; // искомое время
    wprintf(L"Lambda index sort - 2, sec: %f (size - %zi, first - %lu, last - %lu) \n", search_time2 / 1000.0, vlong.size(), vlong[0], vlong[vwchar.size() - 1]);
 
    //Pair sort New - №3.1-первый метод
    unsigned int start_time31 = clock(); // начальное время
    std::vector<str_index> pairs(vwchar2.size());
    for (size_t i = 5; i < vwchar2.size(); ++i)
        pairs[i] = str_index{ i, vwchar2[i] };
    std::sort(pairs.begin(), pairs.end());
    std::vector<size_t> out(pairs.size());
    std::transform(pairs.begin(), pairs.end(), out.begin(), [](const str_index& i) {return i.index; });
    unsigned int end_time31 = clock(); // конечное время
    wprintf(L"Pair sort New - 3.1, sec: %f  \n", (end_time31 - start_time31) / 1000.0);
 
    //Pair sort  - №3.2-второй метод
    unsigned int start_time32 = clock(); // начальное время
    std::vector<size_t> sorted_indexes3(vwchar2.size());
    for (size_t i = 0; i < sorted_indexes3.size(); ++i) sorted_indexes3[i] = i;
    
    std::vector<std::wstring> vwchar3(vwchar2.size()); //перекладываем wchar_t* в std::wstring
    for (int i = 5; i < vwchar2.size(); i++) {
        std::wstring wstr3(vwchar2[i]);
        vwchar3[i] = wstr3;
    }
    std::vector<std::pair<size_t, std::wstring>> pair_copy3(vwchar3.size());
    for (size_t i = 0; i < sorted_indexes3.size(); ++i) pair_copy3[i] = std::make_pair(i, vwchar3[i]);
    std::sort(pair_copy3.begin(), pair_copy3.end(),
        [](const std::pair<size_t, std::wstring>& l, std::pair<size_t, std::wstring>& r)
    {
        return l.second < r.second;
    });
    std::vector<long> vlong3(vwchar2.size());
    for (int i = 0; i < pair_copy3.size(); i++) vlong3[i] = pair_copy3[i].first; //переклыдываем pair в массив индексов 
    unsigned int end_time32 = clock(); // конечное время
    wprintf(L"Pair sort - 3.2, sec: %f  \n", (end_time32 - start_time32) / 1000.0);
 
    //Pointer sort  - №4
    unsigned int start_time4 = clock();
    std::vector<str_index> pair_ptrs4(vwchar2.size());
    for (uint32_t i = 5; i < vwchar2.size(); ++i) pair_ptrs4[i] = str_index{ i, vwchar2[i] };
    std::sort(pair_ptrs4.begin(), pair_ptrs4.end());
    std::vector<long> vlong4(vwchar2.size());
    for (int i = 0; i < pair_ptrs4.size(); i++) vlong4[i] = pair_ptrs4[i].index; //переклыдываем pair в массив индексов 
    unsigned int end_time4 = clock();
    wprintf(L"Pointer sort - 4, sec: %f  \n", (end_time4 - start_time4) / 1000.0);
    
    _wsystem(L"pause");
    return 0;
}
Тест:
х64
Simple sort - 1, sec: 0.660
Lambda index sort - 2, sec: 0.968
Pair sort New - 3.1, sec: 0.62600
Pair sort - 3.2, sec: 0.452000
Pointer sort - 4, sec: 0.624000

х32
Simple sort - 1, sec: 0.677000
Lambda index sort - 2, sec: 0.909
Pair sort New - 3.1, sec: 0.57500
Pair sort - 3.2, sec: 0.530000
Pointer sort - 4, sec: 0.572000

Итого даже с переводом в std::wstring, старый/третий метод быстрее всех. New man, у вас так же?
0
301 / 213 / 74
Регистрация: 23.05.2011
Сообщений: 970
Завершенные тесты: 6
20.11.2018, 01:07 19
x86
Simple sort - 1, sec: 1.224000 (size - 2000000, first - 0, last - (null))
Lambda index sort - 2, sec: 1.278000 (size - 2000000, first - 1952412, last - 4)
Pair sort New - 3.1, sec: 0.784000
Pair sort - 3.2, sec: 0.985000
Pointer sort - 4, sec: 0.732000
x64
Simple sort - 1, sec: 0.978000 (size - 2000000, first - 0, last - (null))
Lambda index sort - 2, sec: 1.232000 (size - 2000000, first - 1952412, last - 4)
Pair sort New - 3.1, sec: 0.896000
Pair sort - 3.2, sec: 0.990000
Pointer sort - 4, sec: 0.890000
У Вас какой процессор? С какими опциями компилятора запускаете? Я запускаю с дефолтным оптимизатором Visual Studio (Release).

Добавлено через 3 минуты
Цитата Сообщение от bedvit Посмотреть сообщение
std::vector<wchar_t*> vwchar2(vwchar); //делаем копию массива для Lambda index sort, Pair sort,Pointer sort
Вот это зачем, если сам массив vwchar2 дальше не меняется?

Добавлено через 5 минут
UPD Увидел.

Добавлено через 32 минуты
Среднее по 50 запускам:
Simple sort - 1, sec: 1.015120
Lambda index sort - 2, sec: 146.467580
Pair sort New - 3.1, sec: 0.956940
Pair sort - 3.2, sec, sec: 1.140900
Pointer sort - 4, sec, sec: 0.950100
Кликните здесь для просмотра всего текста

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <thread>
#include <algorithm>
#include <numeric>
#include <string>
#include <iostream>
#include <array>
 
//Lambda index sort - №2
bool comparestring(wchar_t* lhs, wchar_t* rhs)
{
    if (lhs == NULL) return false;
    if (rhs == NULL) return true;
    return wcscmp(lhs, rhs) < 0;
}
 
//Pointer sort  - №4
struct str_index
{
    size_t index;
    const wchar_t* wstr;
    friend bool operator<(const str_index& l, const str_index& r);
    friend bool operator==(const str_index& l, const str_index& r);
    friend bool operator!=(const str_index& l, const str_index& r) { return !(l == r); }
    friend bool operator>(const str_index& l, const str_index& r);
};
 
bool operator<(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return r.wstr != nullptr;
    if (r.wstr == nullptr) return false;
    return wcscmp(l.wstr, r.wstr) < 0;
}
 
bool operator==(const str_index& l, const str_index& r)
{
    return l.wstr == r.wstr ||
        l.wstr != nullptr && r.wstr != nullptr && wcscmp(l.wstr, r.wstr) == 0;
}
 
bool operator>(const str_index& l, const str_index& r)
{
    if (l.wstr == nullptr) return false;
    if (r.wstr == nullptr) return true;
    return wcscmp(l.wstr, r.wstr) > 0;
}
 
std::array<double, 5> measure(const size_t len)
{
    std::array<double, 5> outa = {};
    std::vector<wchar_t*> vwchar(len);
    for (long i = 5; i < vwchar.size(); i++)
    {
        std::wstring wstTmp = std::to_wstring(rand() % (2 << ((15 + 8) - 1)));
        //строка/целое число в интервале [0; 2^(15+8))
        vwchar[i] = new wchar_t[wcslen(wstTmp.c_str()) + 1]; //выделим необходимую память
        wcscpy(vwchar[i], wstTmp.c_str()); //Заполняем массив строк
    }
    std::vector<wchar_t*> vwchar2(vwchar); //делаем копию массива для Lambda index sort, Pair sort,Pointer sort
 
    //Simple sort - №1
    unsigned int start_time = clock(); // начальное время
    std::sort(vwchar.begin(), vwchar.end(), comparestring); //сортируем
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    //wprintf(L"Simple sort - 1, sec: %f (size - %zi,  first - %Ls, last - %Ls) \n", search_time / 1000.0,
    //  vwchar.size(), vwchar[0], vwchar[vwchar.size() - 1]);
    outa[0] = search_time / 1000.0;
 
    //Lambda index sort - №2
    std::vector<long> vlong(vwchar2.size());
    std::iota(std::begin(vlong), std::end(vlong), 0); //заполняем массив индексов
    unsigned int start_time2 = clock(); // начальное время
    std::sort(vlong.begin(), vlong.end(), [&vwchar2](long a, long b)
    {
        return comparestring(vwchar2[a], vwchar2[b]);
    }); //сортируем массив индексов по данным массива строк
    unsigned int end_time2 = clock(); // конечное время
    unsigned int search_time2 = end_time2 - start_time2; // искомое время
    //wprintf(L"Lambda index sort - 2, sec: %f (size - %zi, first - %lu, last - %lu) \n", search_time2 / 1000.0,
    //        vlong.size(), vlong[0], vlong[vwchar.size() - 1]);
    outa[1] = start_time2 / 1000.0;
 
    //Pair sort New - №3.1-первый метод
    unsigned int start_time31 = clock(); // начальное время
    std::vector<str_index> pairs(vwchar2.size());
    for (size_t i = 5; i < vwchar2.size(); ++i)
        pairs[i] = str_index{i, vwchar2[i]};
    std::sort(pairs.begin(), pairs.end());
    std::vector<size_t> out(pairs.size());
    std::transform(pairs.begin(), pairs.end(), out.begin(), [](const str_index& i) { return i.index; });
    unsigned int end_time31 = clock(); // конечное время
    //wprintf(L"Pair sort New - 3.1, sec: %f  \n", (end_time31 - start_time31) / 1000.0);
    outa[2] = (end_time31 - start_time31) / 1000.0;
 
    //Pair sort  - №3.2-второй метод
    unsigned int start_time32 = clock(); // начальное время
    std::vector<size_t> sorted_indexes3(vwchar2.size());
    for (size_t i = 0; i < sorted_indexes3.size(); ++i) sorted_indexes3[i] = i;
 
    std::vector<std::wstring> vwchar3(vwchar2.size()); //перекладываем wchar_t* в std::wstring
    for (int i = 5; i < vwchar2.size(); i++)
    {
        std::wstring wstr3(vwchar2[i]);
        vwchar3[i] = wstr3;
    }
    std::vector<std::pair<size_t, std::wstring>> pair_copy3(vwchar3.size());
    for (size_t i = 0; i < sorted_indexes3.size(); ++i) pair_copy3[i] = std::make_pair(i, vwchar3[i]);
    std::sort(pair_copy3.begin(), pair_copy3.end(),
              [](const std::pair<size_t, std::wstring>& l, std::pair<size_t, std::wstring>& r)
              {
                  return l.second < r.second;
              });
    std::vector<long> vlong3(vwchar2.size());
    for (int i = 0; i < pair_copy3.size(); i++) vlong3[i] = pair_copy3[i].first;
    //переклыдываем pair в массив индексов 
    unsigned int end_time32 = clock(); // конечное время
    //wprintf(L"Pair sort - 3.2, sec: %f  \n", (end_time32 - start_time32) / 1000.0);
    outa[3] = (end_time32 - start_time32) / 1000.0;
 
    //Pointer sort  - №4
    unsigned int start_time4 = clock();
    std::vector<str_index> pair_ptrs4(vwchar2.size());
    for (uint32_t i = 5; i < vwchar2.size(); ++i) pair_ptrs4[i] = str_index{i, vwchar2[i]};
    std::sort(pair_ptrs4.begin(), pair_ptrs4.end());
    std::vector<size_t> vlong4(vwchar2.size());
    for (int i = 0; i < pair_ptrs4.size(); i++) vlong4[i] = pair_ptrs4[i].index; //переклыдываем pair в массив индексов 
    unsigned int end_time4 = clock();
    //wprintf(L"Pointer sort - 4, sec: %f  \n", (end_time4 - start_time4) / 1000.0);
    outa[4] = (end_time4 - start_time4) / 1000.0;
 
 
    for (wchar_t* vwchar1 : vwchar)
    {
        delete[] vwchar1;
    }
 
    return outa;
}
 
int main()
{
    std::array<double, 5> res = {};
    for (size_t i = 0; i < 50; ++i)
    {
        std::array<double, 5> curr = measure(2000 * 1000);
        for (size_t j = 0; j < res.size(); ++j)
            res[j] += curr[j];
        std::cout << i << " run\n";
    }
 
    for (double& re : res)
        re /= 50;
 
    wprintf(L"Simple sort - 1, sec: %f \n", res[0]);
    wprintf(L"Lambda index sort - 2, sec: %f \n", res[1]);
    wprintf(L"Pair sort New - 3.1, sec: %f \n", res[2]);
    wprintf(L"Pair sort - 3.2, sec, sec: %f \n", res[3]);
    wprintf(L"Pointer sort - 4, sec, sec: %f \n", res[4]);
    return 0;
}


Добавлено через 11 минут
P.S. На сайте rextester.com вообще по-другому выходит, например.
Simple sort - 1, sec: 7.189000 (size - 20000, first - 1000346, last - (null))
Lambda index sort - 2, sec: 7.652000 (size - 20000, first - 11437, last - 1)
Pair sort New - 3.1, sec: 7.150000
Pair sort - 3.2, sec: 17.997000
Pointer sort - 4, sec: 7.345000
0
633 / 193 / 20
Регистрация: 20.05.2016
Сообщений: 773
Записей в блоге: 12
20.11.2018, 13:21  [ТС] 20
убрал #define _CRT_SECURE_NO_WARNINGS, изменил wcscpy на wcscpy_s.
Цитата Сообщение от New man Посмотреть сообщение
У Вас какой процессор? С какими опциями компилятора запускаете? Я запускаю с дефолтным оптимизатором Visual Studio (Release).
Microsoft Visual Studio Community 2017
Версия 15.5.6
Библиотека времени выполнения - Многопоточная (/MT)
Оптимизация - "по умолчанию" см. рис.1

Создал новый проект, кроме библиотеки времени выполнения ничего не менял.

Тест, рис.2 на оборудовании:
ЦП - QuadCore Intel Core i7-3770, 3700 MHz (37 x 100)
Системная память 16348 МБ (DDR3-1600 DDR3 SDRAM)

Тест, рис.3 на оборудовании:
ЦП - Intel Xeon E7-4830, 2.3 GHz (2 процессора)
Системная память 3 ГБ
0
Миниатюры
Эффективный алгоритм сортировки одного массива по данным другого массива   Эффективный алгоритм сортировки одного массива по данным другого массива   Эффективный алгоритм сортировки одного массива по данным другого массива  

IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.11.2018, 13:21

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Как проверить вхождение ключей одного массива в ключи другого массива?
Есть два массива $arrayWord = , 1=&gt;, 2=&gt;, 3=&gt; ]; ...

Возможно ли добавить элемент из одного массива к элементу другого массива?
Привет всем программистам. У меня вопрос. Возможно ли добавить элемент из одного массива к элементу...

Записать строку одного массива как столбец другого массива
Ну в общем-то нужна программа, чтобы записать строку одного массива как столбец другого. (поворот...

Сравнить элемент одного массива со всеми элементами другого массива
Есть массив с разрешеными символами (английский алфавит) И есть массив со всеми введёнными...


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

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

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