Язык Си. Создать 10^6 матриц размерности 20 на 30

[Ar2emiS]

Создать 10^6 матриц размерности 20 на 30, элементы которой 0 и 1, далее отобрать из них все различные, записать отобранные матрицы в файл.

[ura_111]

Да, прикольная задача...

Вот сделал: "создание миллиона массивов, размерности 20х30". По сути это треть твоего задания...

1.jpg

Выявил:
1) Пытался объявить тип "int" для массива "a[20][30]", но у меня вывело ошибку(не знаю в чём проблема)... Поэтому изменил на тип "bool" (см. рисунок) - и вроде прокатило. Напомню - тип "bool" предполагает всего 2-а значения "false/ true", что соответствует (у тебя в задании) - "0/ 1". Не знаю, допустимо ли это?
2) Отдельный вопрос по времени выполнения программы. Я засекал: от момента запуска программы и до вывода надписи в консоль у меня получилось 11сек... Попробуй у себя запустить программу, сколько она будет выполняться? Напомню, программа пока что "создаёт миллион массивов" и всё; можно только предположить сколько она будет выполняться по времени, когда будет полностью завершена. Ведь во второй части задания нужно сравнить каждый массив (по элементно) со всеми последующими массивами. ПРЕДСТАВЛЯЕШЬ СКОЛЬКО БУДЕТ СОЧЕТАНИЙ? А, СКОЛЬКО ЭТО ВРЕМЕНИ ЗАЙМЁТ? Вот я и подумал, может в задании ошибка?..
3) Пытался создать массивы "статически" - вывело ошибку. Поэтому изменил на динамическое распределение памяти - вроде прокатило. Но я не знаю: вы такое изучали?
4) Я заполняю массивы "случайным образом", используя функцию "rand" (найди её на картинке). А может нужно в ручную заполнять?
5) Зачем я ввел массив "bool c[1000000]", который вроде нигде не используется... Это нужно для дальнейшего вывода в файл: я предполагаю, что после проверки каждого массива на "одинаковость" с остальными массивами, в "с[1000000]" будет отмечаться: есть ли ещё одинаковые с конкретным массивом или нет... А в дальнейшем, по этим данным, записывать конкретный массив в файл или нет (не даром у "c" миллион элементов - столько и матриц 20x30).

p.s.: а ты ждешь пока кто-то не решит твою задачу или готов сам подключиться к работе? Какой твой уровень подготовки в си?

[Ar2emiS]

По поводу времени выполнения работы, это не быстро, потому что большой объем данных, да и вычисления в конечно счете будут проводится не на обычном компьютере. Просто создать 10^6 матриц, это я сделал. В задании нет ошибки. В этом и проблема, что много сочетаний, то есть каждая матрица из этих 10^6 сравнивается в теми, которые уже вошли в файл.(первая матрица из 10^6 априори входит в файл).
Готов подключиться к работе.
Я то написал по сути эту программу, но это работает только лишь для малого количества матриц, при большом количестве матриц, программа завершает работу.

#include <stdio.h>
#include <locale.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{
 
    srand(time(NULL)); 
    int random,n=20,l,k=30; //k-количество строк, l-количество матриц, n-количество столбцов
       
printf("Input l="); 
scanf("%d", &l);
 
    int c=1,flag; //с-количество вошедших матриц при условии,что одна матрица уже вошла во множество
    double dd=0,D0=1;    //D0-расстояние между матрицами
long int M[l][k][n];
    int H[k][n];
    
      for (int i=0; i<k; i++)   //первичная матрица,входит во множество
      {
        for (int j=0; j<n; j++)
        {
         random=rand()%10;
         if ((random>=0)&&(random<=4))
         M[0][i][j]=0;
         else
         M[0][i][j]=1;
         printf("%d ",M[0][i][j]); 
              
        }
      
       printf("\n");
      }
       
       printf("\n");
 
 
for (int t=1; t<l; t++)       
{
  for (int i=0; i<k; i++)
  {
    for (int j=0; j<n; j++)
    {
    random=rand()%10;
    if ((random>=0)&&(random<=4))
    H[i][j]=0;
    else
    H[i][j]=1;     
    }
  }
 
double D[c];    
flag=999;
 
  for (int q=0; q<c; q++)
  { 
  dd=0;
    for (int i=0; i<k; i++)      //рассчет евклидового расстояния
    {
      for (int j=0; j<n; j++)
      { 
      dd=dd+pow((M[q][i][j]-H[i][j]),2);
      }
    }
  D[q]=sqrt(dd);
  }
 
  for (int q=0; q<c; q++) //если все расстояния между новой матрицей и уже вошедшими во множество матрицами больше D0
  {
  if (D[q]<D0) 
  flag=0;      //flag=0 если матрица не входит во множество
  }
      
  if (flag==999)        //включение новой матрицы во множество
  {
    for (int i=0; i<k; i++)      
    {
      for (int j=0; j<n; j++)
      { 
      M[c][i][j]=H[i][j];
      }
    }
  c++;                   //считает сколько матриц вошло во множество
  } 
}
     
printf("%d\n",c);
return 0;
}

Пожалуйста, оформляйте Ваш код согласно правилам.

[ura_111]

Покажи, что написал.

[Ar2emiS]

Различие между матрица считается как евклидово расстояние.

[ura_111]

1) Перечитай моё вышенаписанный пост (я там не много добавил во время 11: 20- не знаю успел ли ты прочитать...)

2) Уважаемый, нельзя создавать "статический массив" (int M[l][k][n]) с заведомо неизвестным кол-вом элементов. Если количество элементов в массиве должно определяться "потом", тогда нужно применять "динамическое распределение памяти".
Вы такое изучали?

3) А где в программе "миллион массивов"?

[Ar2emiS]

С динамическим выделением памяти не работал. Могли бы Вы тогда изменить в коде, как нужно..?
Переменная l - это и есть количество матриц ( 10^6), просто не присваивал ей сразу 10^6, чтобы проверять правильность работы программы на меньшем количестве матриц.

[ura_111]

Перепиши у себя. Посмотри что понятно, что нет...

2.jpg

Небольшую ошибку обнаружил: все матрицы квадратные. Где ошибся и как поправить?

p.s.: должно быть так.

3.jpg

Ещё одну ошибку заметил: убери из программы переменную "int random;".

[GreenWizard]

чисто соображения:
1) тут, конечно, написано "генерируем матрицы и потом фильтруем", но можно было бы генерировать одну матрицу, проверять на уникальность и потом сохранять... тоже ведь "генерируем и фильтруем", но памяти жрёт на порядки меньше
2) 20х30 - это 600 ячеек... 1.000.000 матриц - 600.000.000 ячеек... если bool - 600 Mb, int - 2.4Gb... если же учесть "бинарную природу", то можно 8 ячеек кодировать одним байтом, а 600 / 8 - аккурат 75 байт... тогда уже и памяти нужно всего 75мб..... если идти дальше, то тут, теоретически, 600 вызовов rand можно заменить 75ю и тупо генерировать целый байт (но может измениться распределение 0 и1, так что, если это имеет значение, то не прокатит трюк)...... сравнение матриц "в лоб" - сравнение 75 байт, опять же
3) мне не совсем понятно, что за "декартово расстояние между матрицами", но если нужно тупо уникальные матрицы получить и важна скорость, то можно уникальные сохранять не в массив, а в хеш-таблицу массивов... если ограничиться 1 байтом/ключ, и подобрать более-менее равномерный хеш, то будет, например, сравнение не с 10,000 уникальных матриц, а с 10,000 / 256 т. е. с 39 матрицами (конечно, в реальности не всё так круто, но всё равно быстрее, чем наивный вариант)... но это так, уже не уровень новичков) хотя влепить массив на 256 массивов - не сложно

[ViktorR]

Опять же вариант:
- Генерируем случайную последовательность из 75-и не повторяющихся чисел со значением от 0 до 255. Это наша первая матрица, в которой все байты заведомо уникальны (из 256-и состояний всегда можно выбрать 75 не повторяющихся ).
Пишем ее в файл. Далее генерируем, методом перестановок байтов, новые матрицы и сразу пишем в файл. Новые матрицы будут уникальными по определению. Память для данных - на 75 байт основной матрицы и на 75 байт вновь генерируемой. Если необходимо писать 1 и 0 в символьном виде, то перед записью в файл проводить обработку (сдвигаем 75 байт и выдвинутый бит + '0' пишем в файл). Да, со временем напряг, но основное время, как понимаю, работа с файлом.

Как-то так, ...