За масив в C

Става дума от даден двумерен масив да се изкарат елементите , които не се повтарят в масива и да се запише броя на различните елементи. Мислих мислих , голямо мислене и пак немога да го измисля. Ако някой може, да се обажда.

Няма пряк път до мястото, където си заслужава да идем Бевърли Силс

На първо време ще ти кажа, че това колко мерен е масивът няма никакво отношение към задачата ти.
Предполагам, че може да има някой хитър алгоритъм със сложност N*Log(N), но най-елементарно е да си хванеш всеки елемент и да проверяваш дали има някой с неговата стойност след и преди него. Сожността е N^2, ама нали ще върши работа.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Ami eto ti go i hitriq - sortirash go sys slojnost N*Log(N), i posle go minavash 1 pyt i vijdash koi se povtarqt.

Mojesh da polzvash i dopulnitelna structura ot danni, sortiran masiv, durvo ili hash tablica i sled kato preminash prez element proveriavash v structurata dali go ima, ako ne go insertvash i t.n. Pri dvoichno durvo i sortiran masiv slojnostta ste ti e ~ O(N*log(N)), pri hash tablica oste po dobre ~ O(N).

Ето ти го наготово алгоритъмът, описан от Colombino (ако не съм оплескал нещо, че не съм го тествал сериозно). Сравняваш всеки със всеки елемент.

#include <stdio.h>



int cnt_diff(int *a, int n)

{

	int i, j, cnt = 0;

	for (i = 0; i < n; i++) {

		for (j = 0; j < n; j++)

			if ((a[ i] == a[j]) && (i != j))

				break;

		if (j == n)

			++cnt;

	}

	return cnt;

}



int main()

{

	int a[] = { 4, 5, 7, 5, 9 };

	printf("%d\n", cnt_diff(a, sizeof(a)/sizeof(*a)));

	return 0;

}

Сега можеш сам да се пробваш да го оптимизираш, напр. с използването на допълнителен масив, в който да пазиш повторилите се елементи, та вътрешния цикъл да го въртиш от i, вместо от 0, но ще трябва естествено да проверяваш и в допълнителния.

Да, става, ако имаш право да го бараш, или да алокираш памет.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Не забравяй, че системата е бъгава и като излезеш от pre продължава да не слага нови редове, та трябва да си праскаш Enter, ако искаш да не те четат през "View Source".



System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

> Не забравяй, че системата е бъгава и като излезеш от pre продължава да не слага нови редове, та трябва да си праскаш Enter, ако искаш да не те четат през "View Source".

Ами изобщо не го бях видял този момент, понеже в Linux ползвам Galeon, а в Windows - Phoenix и те го нямат този проблем. Пуснах специално IE, след като прочетох какво си написал, и наистина го реже неприятно.

Иначе нарочно сложих интервал в [ i], за да не го изтрие и да обърне всичко в italic.

За в бъдеще ще се стараем повече.

Всъщност обхождай само напред. Ако има повтаряш се елемент и ходиш и назад ще изкара по примера че 5 се повтаря два пъти а то се повтаря един. ( Хм! Различно тълкуване на думата 'повтаря'? )

> Всъщност обхождай само напред. Ако има повтаряш се елемент и ходиш и назад ще изкара по примера че 5 се повтаря два пъти а то се повтаря един. ( Хм! Различно тълкуване на думата 'повтаря'? )

Няма двусмислие, понеже се търси броят на елементите, които се срещат само веднъж. Аз си обхождам само напред, ама няма как да си спестиш започването отначало във вътрешния цикъл (освен ако не поддържаш допълнителен масив), защото някой елемент, който вече си го отсял като повтарящ се, изведнъж ще решиш, че го срещаш за първи път.

Аз лично бих направил обхождането във вътрешния цикъл с два последователни цикъла - от 0 до I и от I+1 до N. Това за извеждането на уникалните. А за да разберем броят на повтарящите се елементи, можем да го увеличваме само тогава, когато в първия вътрешен цикъл елементът се среща само един път. (т.е. ще се наложи да излизаме аварийно от него само при второ срещане на елемента ). Със сигурност има и други начини.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Eto i algorithm s O(n*log(n)) slojnost (v nai-loshia sluchai). Kolkoto poveche povtariasti se elementi ima tolkova slojnostta namaliava, pri masiv s ednakvi elementi slojnostta e O(N). Kato stranichen rezultat masiva se sortira (burzo).

#include <stdio.h>



void swap(int* a, int* b)

{

  int c;

  c=*a;

  *a=*b;

  *b=c;

}



int qcnt_diff(int* a, int n)

{

  int cnt = 0;

  int d, j, l, m, r;



  m = a[l = r = n/2];

  while(l > 0 && a[--l] == m)

    ;

  while(r < n && a[++r] == m)

    ;



  j = 0;

  while(j <= l)

  {

    if(!(d = (a[j] - m)))

      swap(&a[j], &a[l--]);

    else if(d > 0)

      swap(&a[j], &a[--r]);

    else

      j++;

  }



  j = n-1;

  while(r <= j)

  {

    if(!(d=(m - a[j])))

      swap(&a[j], &a[r++]);

    else if(d > 0)

      swap(&a[j], &a[++l]);

    else

      j--;

  }



  l++;

  r--;



  if(l > 0)

    cnt = qcnt_diff(a, l);

    

  if(r < n-1)

    cnt += qcnt_diff(&a[r+1], n-r-1);



  if(l == r) {

    printf("%d\n", m);

    cnt++;

  }



  return cnt;

}



int main()

{

  int a[] = { 5, 3, 3, 1, 2, 4, 4, 0 };

  printf("\ncnt=%d\n\n", qcnt_diff(a, sizeof(a)/sizeof(a[0])));

  return 0;

}

Ако ще сортираме масива, защо да не го направим простичко с библиотечна функция, вместо да го пишем на ръка. Големият и сложен код трудно се пише, трудно се поддържа, трудно се чисти от грешки. Освен това аз не бих използвал рекурсия извън рамките на упражнение, понеже машините все пак обикновено са с ограничен стек.

#include <stdio.h>

#include <stdlib.h>



int int_cmp(const void *i1, const void *i2)

{

	return *(int *)i1 - *(int *)i2;

}



int cnt_diff_s(int *a, int n)

{

	int i, cnt = n;

	for (i = 0; i < n-1; i++)

		if (a[ i] == a[i+1]) {

			--cnt;

			do {

				--cnt;

				if (++i >= n-1)

					break;

			} while (a[ i] == a[i+1]);

		}

	return cnt;

}



int main()

{

	int a[] = { 5, 3, 3, 3, 1, 2, 4, 4, 0 };

	int n = sizeof(a)/sizeof(*a);

	qsort(a, n, sizeof(*a), int_cmp);

	printf("%d\n", cnt_diff_s(a, n));

	return 0;

}

Сега масивът вече се обхожда само веднъж.

Mi primerno stoto iskame da e burzo.

#include <windows.h>

#include <stdio.h>

#include <time.h>



void swap(int* a, int* b)

{

  int c;

  c=*a;

  *a=*b;

  *b=c;

}



void qsort2(int* a, int n)

{

  int d, j, l, m, r;



  m = a[l = r = n/2];

  while(l > 0 && a[--l] == m)

    ;

  while(r < n && a[++r] == m)

    ;



  j = 0;

  while(j <= l)

  {

    if(!(d = a[j] - m))

      swap(&a[j], &a[l--]);

    else if(d > 0)

      swap(&a[j], &a[--r]);

    else

      j++;

  }



  j = n-1;

  while(r <= j)

  {

    if(!(d = m - a[j]))

      swap(&a[j], &a[r++]);

    else if(d > 0)

      swap(&a[j], &a[++l]);

    else

      j--;

  }



  l++;

  r--;



  if(l > 0)

    qsort2(a, l);

    

  if(r < n-1)

    qsort2(&a[r+1], n-r-1);

}





int* CreateTestArray(int siz, int max)

{

  int* arr = (int*)malloc(siz*sizeof(int));

  if(!arr) return 0;



  srand((unsigned)time(0));



  while(siz-->0)

    arr[siz] = rand() % max;

  return arr;

}



int* DuplicateArray(int* src, int siz)

{

  int* arr = (int*)malloc(siz*sizeof(int));

  if(!arr) return 0;



  memcpy(arr, src, siz*sizeof(int));

  return arr;

}



void DestroyTestArray(int* arr)

{

  if(arr)

    free(arr);

}



int compare( const void *arg1, const void *arg2 )

{

   return (*(int*)arg1 - *(int*)arg2);

}



int main()

{

  int siz, max;

  long l;



  siz = 1000000;

  max = 1000;

  int *arr = CreateTestArray(siz, max);

  int *arr1 = DuplicateArray(arr, siz);



  l = GetTickCount();

  qsort2(arr, siz);

  printf("Qsort2 ticks: %d\n", GetTickCount()-l);



  l = GetTickCount();

  qsort(arr1, siz, sizeof(int), compare);

  printf("Qsort ticks: %d\n", GetTickCount()-l);



  while(siz-->0)

    if(arr[siz] != arr1[siz])

      printf("Diff. at %d\n", siz);



  DestroyTestArray(arr);

  DestroyTestArray(arr1);



  return 0;

}

Moia qsort2 sredno e po-burz ot MSVC CRT qsort, a pri gornia test (s maluk range na elementite) e ~10 puti po-burz i to bez da e tuned!
Probvai granichnia sluchai max=2 :))

A, i cnt_diff_s ne e dobre napisana (pone ot pruv pogled :))), ako iskash da dobavish print na razlichnite elementi (kakto choveka iska v uslovieto) za n=1 ste triabva da go obrabotvash explicitno ili da smenish algorituma.

> A, i cnt_diff_s ne e dobre napisana (pone ot pruv pogled :))), ako iskash da dobavish print na razlichnite elementi (kakto choveka iska v uslovieto) za n=1 ste triabva da go obrabotvash explicitno ili da smenish algorituma.

Явно не си я тествал. Отначало бях сложил условие, ако n <=1 да се връща n, но видях, че ако се напише добре, то е излишно, затова и го изтрих.

Да се опитваш да пренаписваш стандартната библиотека е неразумно и арогантно. Най-вече - не се изплаща. Been there, done that.

Сега съм по-смирен и не се опитвам да откривам топлата вода всеки път. Предпочитам да се опра на нещо отдавна изтествано и оптимизирано.

Това, което казваш за скоростта е интересно и заслужава да се провери, ама сега е малко късно. Ако не ме домързи, ще направя един тест през уикенда.

Да, извинявай, прав си за изписването на отделните елементи, това съм го прескочил. Бях се фокусирал само върху броя.

Ама нека човекът да добави и нещо от себе си в домашното.

Нещо вече сам си говоря, ама карай...

Направих тест с gprof. За да е обективен, коментирах печата в твоята функция, а в моята прехвърлих сортирането вътре във функцията, за да се мери и то във времето.

#include <stdio.h>

#include <stdlib.h>



#define SIZE	1000000

int a[SIZE];



int int_cmp(const void *i1, const void *i2)

{

	return *(int *)i1 - *(int *)i2;

}



int cnt_diff_s(int *a, int n)

{

	qsort(a, n, sizeof(*a), int_cmp);

	int i, cnt = n;

	for (i = 0; i < n-1; i++)

		if (a[ i] == a[i+1]) {

			--cnt;

			do {

				--cnt;

				if (++i >= n-1)

					break;

			} while (a[ i] == a[i+1]);

		}

	return cnt;

}



int main()

{

	int i;

	for (i = 0; i < SIZE; i++)

		a[ i] = random();

	printf("%d\n", cnt_diff_s(a, SIZE));

	return 0;

}



Ето ги и резултатите:

Each sample counts as 0.01 seconds.

  %   cumulative   self              self     total

 time   seconds   seconds    calls   s/call   s/call  name

 69.46      1.16     1.16        1     1.16     1.63  qcnt_diff

 28.14      1.63     0.47 25047841     0.00     0.00  swap

  2.40      1.67     0.04                             main



Each sample counts as 0.01 seconds.

  %   cumulative   self              self     total

 time   seconds   seconds    calls  ms/call  ms/call  name

 91.30      0.21     0.21                             int_cmp

  4.35      0.22     0.01        1    10.00    10.00  cnt_diff_s

  4.35      0.23     0.01                             main

Както виждаш, разликата е около осем пъти. Това, което ти правиш за 1.63s, при мен става за 0.21. Не мога да кажа, че съм изненадан.

Това е без всякакви оптимизации, тъй че не е съвсем коректно, понеже библиотеката вероятно е компилирана с оптимизации. Тествана с -O3 на gcc твоята програма става доста по-бърза:

index % time    self  children    called     name

                                                 <spontaneous>

[1]    100.0    0.03    0.53                 main [1]

                0.53    0.00       1/1           qcnt_diff [2]

-----------------------------------------------

                              999751             qcnt_diff [2]

                0.53    0.00       1/1           main [1]

[2]     94.6    0.53    0.00       1+999751  qcnt_diff [2]

                              999751             qcnt_diff [2]

-----------------------------------------------

Вече се изпълнява само за 0.53s. Разликата обаче пак си остава два пъти и половина.

Виждам, че всички са заети да измислят топлата вода. Сортировки, функции swap i t.n.


#include "stdafx.h"
#include <algorithm>
#include <iostream>

using namespace std;

void remove_duplicates (int *ar, int size)
{
sort (ar, ar + size);
unique_copy(ar, ar+size, ostream_iterator<int>( cout, " "));
}

int main(int argc, char* argv[])
{
int ar[] = {0,1,2,44,1,1,3,45,67,8,8,0,2,2};

remove_duplicates (ar, 14);
return 0;
}

Iavno versiata na qsort s koiato testvash e dosta dobra. Moia test po-gore beshe za VC6. S VC7 qsort-a e dosta po-dobur, no vse oste moia e po-burz makar i s konstanta, veche ne se poluchava razlika v puti. Mislia che ako se napravi tune na moiata vesria s vzimane na po-dobra mediana, insert sort pri maluk broi elementi i se mahne rekursiata moje oste sustestveno da se uskori. Mejdu drugoto mojesh li da vidij kakvi optimizacii e napravil kompilatora pri tebe, dali e inline-al swap-a, smenil li e vtoria recursiven call s jmp? Mojesh li da probvash i s poveche povtariasti se elementi primerno a[ i] = random() % 1000, a[ i] = random() % 100, a[ i] = random() % 10; I da vidij dali razlikata namaliava t.e. dali razlikata se poluchava ot algorituma ili glavno ot implementaciata.