GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (7)След. > >>   Поиск:  
 Автор Тема: Задачка на сообразительность
гость
77.247.181.*
Задачка на сообразительность
Добавлено: 16 янв 19 7:55
Говорят тут водятся кулхацкеры, ну так проверим...

В общем нужно на С или С++ БЫСТРО ПЕРЕМЕШАТЬ в последовательности индексы, к примеру есть 1,2,3,4,5 а нужно чтобы стало что то типа 3,4,2,1,5 ну или 4,5,3,2,1 рандомно, но что бы все индексы присутствовали один раз.

На сишарпе это делается очень просто и быстро(1миллион сэмплов 100мс):

for (int i = 0; i < length; i++) input[i] = i;
input.OrderBy(i => rnd.Int(length)).ToArray();

На С++ стандартными примитивами получается ужасно медленно пол минуты

vector<pair<int, int>> seq;
for (int i = 0; i < N; ++i) seq.push_back(pair<int, int>(rnd.Int(0, N * 100), i));
sort(seq.begin(), seq.end());
vector<int> res;
for (int i = 0; i < N; ++i) res.push_back(seq[i].second);

Только тупо заполнение вектора длится 5 сек


Анука покажите класс кулхацкеры! Говорят что вы тут самые дерзкие, самые красноглазые...
[Ответ][Цитата]
Luarvik.
Сообщений: 16136
На: Задачка на сообразительность
Добавлено: 16 янв 19 7:59
Здесь не программированием занимаются, а разработкой (да будет позволено сказать так громко) СРЕДСТВ программирования.
[Ответ][Цитата]
Ко.В.
Сообщений: 1222
На: Задачка на сообразительность
Добавлено: 16 янв 19 8:31
Изменено: 16 янв 19 8:33
Цитата:
Автор: гость

Говорят тут водятся кулхацкеры, ну так проверим...

В общем нужно на С или С++ БЫСТРО ПЕРЕМЕШАТЬ в последовательности индексы, к примеру есть 1,2,3,4,5 а нужно чтобы стало что то типа 3,4,2,1,5 ну или 4,5,3,2,1 рандомно, но что бы все индексы присутствовали один раз.

На сишарпе это делается очень просто и быстро(1миллион сэмплов 100мс):

for (int i = 0; i < length; i++) input[i] = i;
input.OrderBy(i => rnd.Int(length)).ToArray();

На С++ стандартными примитивами получается ужасно медленно пол минуты

vector<pair<int, int>> seq;
for (int i = 0; i < N; ++i) seq.push_back(pair<int, int>(rnd.Int(0, N * 100), i));
sort(seq.begin(), seq.end());
vector<int> res;
for (int i = 0; i < N; ++i) res.push_back(seq[i].second);

Только тупо заполнение вектора длится 5 сек


Анука покажите класс кулхацкеры! Говорят что вы тут самые дерзкие, самые красноглазые...


Я эту задачу на С++ решал многократно… Элементарно, щас код покажу…
[Ответ][Цитата]
Ко.В.
Сообщений: 1222
На: Задачка на сообразительность
Добавлено: 16 янв 19 8:41
Изменено: 20 янв 19 3:27

// Пусть элементов 100.

int data[100];

// Вначале все элементы упорядочены

for (int i=0; i<100; i++) data[i]=i;

// Квадратичная сложность гарантирует,
// что элементы будут перемешаны с большой вероятностью

for (int i=0; i<100*100; i++)

{
int alfa = irand()%100;

int omega = irand()%100;

int zap=data[omega];

data[omega]=data[alfa];

data[alfa]=zap;
}
[Ответ][Цитата]
гость
77.247.181.*
На: Задачка на сообразительность
Добавлено: 16 янв 19 9:23
Цитата:
Автор: КВ

// Пусть элементов 100.

int data[100];

// Вначале все элементы упорядочены

for (int i=0; i<100; i++) data[i]=i;

// Квадратичная сложность гарантирует,
// что элементы будут перемешаны с большой вероятностью

for (int i=0; i<100*100; i++)

{
int alfa = irand()%100;

int omega = irand()%100;

int zap=data[omega];

data[omega]=data[alfa];

data[alfa]=zap;
}
да нет, это ерунда какая то, нужно не "большой вероятностью" а точно и без квадратичных сложностей и переприсваиванием 100500 раз, попробуйте этот код запустить на миллионе элементов...

у вас помоему с головой не в порядке такое предлагать
[Ответ][Цитата]
Ко.В.
Сообщений: 1222
На: Задачка на сообразительность
Добавлено: 16 янв 19 9:45
Изменено: 16 янв 19 9:46
А кто сказал, что у меня с головой всё в порядке… Есть решения простые и долгие, а есть сложные но быстрые…

Нужно соблюдать баланс… У вас тоже проблемы, но не с головой а с программированием…. УЧИТЕСЬ !!!

Плюс в теории вероятностей - вы дилетант…
[Ответ][Цитата]
Михайло
Сообщений: 2251
На: Задачка на сообразительность
Добавлено: 16 янв 19 10:21
Изменено: 16 янв 19 10:21
Цитата:
Автор: гость 77 (топикстартер)


vector<pair<int, int>> seq;
for (int i = 0; i < N; ++i) seq.push_back(pair<int, int>(rnd.Int(0, N * 100), i));
sort(seq.begin(), seq.end());
vector<int> res;
for (int i = 0; i < N; ++i) res.push_back(seq[i].second);

Только тупо заполнение вектора длится 5 сек

Это ж надо было додуматься к миллиону объектов применить объекты высокого уровня такие как vector<>.
Учи указатели, разыменовывание указателя, выделение памяти под массив malloc() в C++.
[Ответ][Цитата]
Egg
Сообщений: 12785
На: Задачка на сообразительность
Добавлено: 16 янв 19 10:45
Цитата:
Автор: Михайло
выделение памяти под массив malloc() в C++.

Ну, если уж мы за программирование начали, то, Миш, учись дальше, пока - 2
malloc - это сишная операция, если пользуешь плюсы, всегда пользуй new,
это не правило, это закон...
[Ответ][Цитата]
гость
77.247.181.*
На: Задачка на сообразительность
Добавлено: 16 янв 19 10:49
Цитата:
Автор: Михайло


Это ж надо было додуматься к миллиону объектов применить объекты высокого уровня такие как vector<>.
Учи указатели, разыменовывание указателя, выделение памяти под массив malloc() в C++.
ну покажите как, зачем языком чесать попусту, да и вектора вроде как ни придумывали для только учебных примеров, это вполне себе продакшн инсмтрумент

и да... malloc() в с++ это изврат...
[Ответ][Цитата]
гость
77.247.181.*
На: Задачка на сообразительность
Добавлено: 16 янв 19 10:50
Цитата:
Автор: КВ

А кто сказал, что у меня с головой всё в порядке… Есть решения простые и долгие, а есть сложные но быстрые…

Нужно соблюдать баланс… У вас тоже проблемы, но не с головой а с программированием…. УЧИТЕСЬ !!!

Плюс в теории вероятностей - вы дилетант…
не бузите
[Ответ][Цитата]
Ко.В.
Сообщений: 1222
На: Задачка на сообразительность
Добавлено: 16 янв 19 11:00
А я буду бузить… Надеюсь Бузова меня простит…
[Ответ][Цитата]
Михайло
Сообщений: 2251
На: Задачка на сообразительность
Добавлено: 16 янв 19 11:16
Изменено: 16 янв 19 11:22
Цитата:
Автор: гость

и да... malloc() в с++ это изврат...

Под массивы память выделяется быстро с помощью malloc(), calloc(), realloc().
С или С++ - это вообще дело десятое, этот механизм работает быстро везде.

Алгоритм свой не меняйте, просто замените vector на указатель.

Сначала объявите указатели и выделите память под массивы:

int **seq; // двумерный массив
seq = (int**) malloc(M * sizeof(int*)); // двумерный массив размерности MxN - это массив указателей на одномерные массивы размерности N
for (i = 0; i < M; i++)
{
seq[i] = (int*) malloc(N * sizeof(int));
}
int *res; // одномерный массив размерности N
res = (int*) malloc(N * sizeof(int)); // под одномерный массив выделять память проще


Если созданы указатели seq и res, то в дальнейшем можно обращаться к элементам массивов как обычному vector. Например, seq[i][j] или res[i]. Но это работает не так быстро.

Быстрый доступ к элементам осуществляется указателями на элемент и разыменовыванием указателей:

int **seq0; // указатель на элемент массива seq
int *res0; // указатель на элемент массива res
seq0 = seq; // указатель seq0 указывает на самый первый элемент массива seq
seq0++; // теперь на второй
res0 = res; // указатель res0 указывает на самый первый элемент массива res
res0 += 5; // теперь на шестой
x = **seq0; // считывание второго элемента двумерного массива (двойное разыменование - указателя на массив указателей и затем указателя на числа)
y = *res0; // считывание шестого элемента одномерного массива (разыменование указателя на массив чисел)
[Ответ][Цитата]
Egg
Сообщений: 12785
На: Задачка на сообразительность
Добавлено: 16 янв 19 11:24
Цитата:
Автор: Михайло
int **seq0; // указатель на элемент массива seq
int *res0; // указатель на элемент массива res

Правда? Ну тогда дополнительный вопрос: чем отличается * от **?
[Ответ][Цитата]
Михайло
Сообщений: 2251
На: Задачка на сообразительность
Добавлено: 16 янв 19 11:24
Когда вы пишете код, указанный мною выше, вы по сути пишете на языке очень и очень близком к ассемблеру. Не удивлюсь, если Си-шарп сикнет.
[Ответ][Цитата]
гость
77.247.181.*
На: Задачка на сообразительность
Добавлено: 16 янв 19 11:26
Цитата:
Автор: Михайло

Под массивы память выделяется быстро с помощью malloc(), calloc(), realloc().
....
спасибо конечно, но это элементарные занания, я имел в виду показать как решить поставленную задачу за 100мс на миллион элементов
[Ответ][Цитата]
 Стр.1 (7): [1]  2  3  4  5  ...  7След. > >>