Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Info Coronavirus/Vaccinare vs Fake News

Brother Eroare scanare A9

Achizitie auto

Procedura Preschimbare nr verzi p...
 Copiii si obezitatea

Reglare greutate doza Unitra GS-431

Potrivire jante ?

instant sau dus electric?
 Microfon extern pentru ML/DSLR

Schimbare parbriz

Costuri achiziție garsoniera.

Pensii publice - Venit total asig...
 Solutie (lichid pulverizat) pentr...

Backup calling

Ce placa video recomandati si car...

Telecomanda cu touch triplu PNI S...
 

Verificare sortare lista C#

- - - - -
  • Please log in to reply
19 replies to this topic

#1
Bursul

Bursul

    alias Petrov

  • Grup: Senior Members
  • Posts: 44,483
  • Înscris: 30.10.2003
Am urmatoarea lista si am adaugat anumite valori cu functia Add()

List<Int32> list = new List<Int32>();
...
list.Add(varNumar);


Lista are avea urmatoarele valori: {0, 3, 6, 9} sau {1, 7, 9, 5}

Cum verific ca lista e sortata? Din pacate nu stiu sa caut pe net sa gasesc un exemplu care sa se potriveasca cu ce vreau eu. Peste tot e cum sa sortez lista sau cum sa compar valorile a doua liste.

Se poate face cu foreach ceva de genul?

foreeach ( int s in list)
{
...
}

Daca da, cum?
Daca nu, cum altcumva?

Edited by Bursul, 23 May 2022 - 13:40.


#2
Argv

Argv

    Active Member

  • Grup: Members
  • Posts: 1,900
  • Înscris: 25.10.2007
Sortata in ordine crescatoare? In for compari fiecare element cu elementul precedent si daca e mai mare sau egal inseamna ca e sortata.

#3
Nenea Zap

Nenea Zap

    Zuperman

  • Grup: Senior Members
  • Posts: 15,690
  • Înscris: 10.04.2006

Vizualizare mesajBursul, pe 23 mai 2022 - 13:38, a scris:

Cum verific ca lista e sortata?
Peste tot e cum sa sortez lista sau cum sa compar valorile a doua liste.
Daca ai doar astea functii sort() si compare(), cum iti dai seama ca o lista este sortata?
In romana, fara cod.

#4
maccip

maccip

    44 ani

  • Grup: Senior Members
  • Posts: 29,005
  • Înscris: 06.01.2007
int minim=int.MinValue;
bool sortat=true;

foreach(int i in list)
{
   if( i< minim)
   {
	  sortat=false;
	  break;
   }
   minim=i;
}
// aici variabila sortat va avea valoarea care trebuie



#5
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 28,928
  • Înscris: 24.02.2007
Cum depisteaza asta ca 1 2 4 3 nu e sortat?

#6
Bursul

Bursul

    alias Petrov

  • Grup: Senior Members
  • Posts: 44,483
  • Înscris: 30.10.2003

Vizualizare mesajmaccip, pe 23 mai 2022 - 21:04, a scris:

...

Mersi :D Codul ala gaseste minimul din lista, nu e exact ce vreau.

Insa sigur nu m-am exprimat la inceput cum trebuie. Deci avem o lista si speram sa pot face ceva de genul:

foreach ( int s in list)
{
	 if (s.actual > s.urmator)
		 Eroare
}


Nu intreb de algoritm in sine, ci intrebarea tine mai mult de C#, daca se poate verifica simplu daca o lista e ordonata crescator sau descrescator. Poate e o functie de genul: list.isSort().
De exemplu exista functie care iti sorteaza automat lista: list.Sort(). Poate era si o functie care sa verifice.

Doream sa scap de "for".

#7
maccip

maccip

    44 ani

  • Grup: Senior Members
  • Posts: 29,005
  • Înscris: 06.01.2007
Nu cred sa existe o asemenea functie in librarie, insa functiile din librarie nu sunt mai presus de cele scrise de tine.
Daca vrei sa para mai "dă librărie", atunci poti folosi "Extension Methods in C#" pentru clasa List<int> .Chestia asta a fost introdusa mai tarziu in C#, pe la versiunea 3.0 parca.

Adica scrii functia care testeaza daca e sortata cam asa...
public static bool IsSorted(this List<int> list)
{
		 //bla bla bla
}


Si o folosesti in codul tau ca si cum ar fi parte din List<>, "dă librărie", cam asa.

if( list.IsSorted() )
{
//bla bla bla
}


Acuma, deoarece limbajul permite existenta acestor extensii, care aduc mai multa functionalitate unei clase in afara acestei clase, exista teoretic posibilitatea ca extensia care face IsSorted() sa existe undeva (altundeva decat in List<> ). Si cat timp exista aceasta posibilitate, cum non-existenta nu poate fi dovedita decat prin cautare exhaustiva in toata libraria, e greu de dat raspuns solid la aceasta intrebare.
Daca aceasta extensie ar exista intr-un anume DLL si sub un anume namespace, atunci trebuie referit acel DLL la proiect si acel namespace
using DăLibrărieExtensionNamespace;

Pentru ca apoi, IDE-ul sa-ti recunoasca extensia (sa ti-o arate dupa ce pui punctul dupa o lista) si pentru a o putea folosi.

Dar mai bine o scrii tu, ca nu-i cu nimic mai prejos fata de una din librarie.

Edited by maccip, 24 May 2022 - 10:11.


#8
radu103

radu103

    Senior Member

  • Grup: Senior Members
  • Posts: 7,482
  • Înscris: 15.11.2003
e mai siplu sa te asiguri ca e sortata asa de cate ori ai nevoie.

list.Sort( e => e.element);

sau cu linq

pets = pets.OrderBy(pet => pet.Age).toList()

Logica spune ca ai nevoie oricum de sortare daca vrei s-o verifici asa ca de ce ai mai consuma timp cu verificarea ?

Referinte
https://docs.microso...by?view=net-6.0
https://docs.microso...rt?view=net-6.0

View PostBursul, on 24 mai 2022 - 08:43, said:

De exemplu exista functie care iti sorteaza automat lista: list.Sort(). Poate era si o functie care sa verifice.
Pentru ca se sorteaza cand ai nevoie, nu se mai verifica.
S-a eliminat pasul de verificare ptr ca nu are sens, oricum ai nevoie de ea sortata mai departe asa ca o sortezi si gata
Sortarea aplicata (inutil) pe o lista deja sortata este fix la fel de costisitoare ca verificarea daca e sortata scrisa manual de utilizator ptr ca oricum a fost eliminata din framework ca fiind operatie inutila

Edited by radu103, 24 May 2022 - 10:17.


#9
Nenea Zap

Nenea Zap

    Zuperman

  • Grup: Senior Members
  • Posts: 15,690
  • Înscris: 10.04.2006

 Nenea Zap, pe 23 mai 2022 - 14:49, a scris:


Daca ai doar astea functii sort() si compare(), cum iti dai seama ca o lista este sortata?
In romana, fara cod.
Tot nu ai răspuns la întrebarea asta.
Așa afli și cum arată codul.

#10
maccip

maccip

    44 ani

  • Grup: Senior Members
  • Posts: 29,005
  • Înscris: 06.01.2007
Sort() dureaza O(n log(n)) iar IsSort() dureaza doar O(n).

#11
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 28,928
  • Înscris: 24.02.2007

View PostBursul, on 24 mai 2022 - 08:43, said:

Nu intreb de algoritm in sine, ci intrebarea tine mai mult de C#, daca se poate verifica simplu daca o lista e ordonata crescator sau descrescator. Poate e o functie de genul: list.isSort().

C++ are https://en.cpprefere...rithm/is_sorted
.NET nu stiu sa aibe, dar e banal de scris/generalizat pentru ICollection<>

#12
parabellum

parabellum

    Senior Member

  • Grup: Senior Members
  • Posts: 2,056
  • Înscris: 06.01.2010

Quote

Logica spune ca ai nevoie oricum de sortare daca vrei s-o verifici asa ca de ce ai mai consuma timp cu verificarea ?
Logica nu spune neaparat asta, dar in general, functie de algoritmul de sortare, s-ar putea sa nu fie O(N) pe 'best case scenario':
https://en.wikipedia...n_of_algorithms

#13
Bursul

Bursul

    alias Petrov

  • Grup: Senior Members
  • Posts: 44,483
  • Înscris: 30.10.2003

Vizualizare mesajNenea Zap, pe 24 mai 2022 - 10:24, a scris:

Tot nu ai răspuns la întrebarea asta.
Așa afli și cum arată codul.
Doream o solutie rapida, nu am timp de dezbateri.

Dpmdv subiectul e terminat. S-a rezolvat cu un for, nu e ceea ce am vrut, dar isi face treaba. Consider ca nu se poate face cum am vrut eu, asta e, astept pe aia de la MS sa vina cu ceva mai inteligent :lol:

#14
maccip

maccip

    44 ani

  • Grup: Senior Members
  • Posts: 29,005
  • Înscris: 06.01.2007
Microsoft au o privire mai lolistica asupra a ceea ce pun in librarii.
IsSorted nu e o functie care sa foloseasca la ceva din mai multe puncte de vedere.

Asta pentru ca, de regula un algoritm "bine facut", are nevoie sa afle daca IsSorted() si apoi are nevoie imediat de prima valoare pentru care IsSorted() face sa returneze false, iar metoda IsSorted() asa cum este ea, nu poate returna decat acel boolean. Daca ti-a returnat false, atunci se presupune ca trebuie sa faci ceva cu lista aia, incepand tocmai din pozitia unde ti-a dat fail la verificarea sortarii.
Altfel, functia ar fi doar una de tip informativ, care returneaza un singur bit de informatie cu privire la o cantitate posibil uriasa de informatie. In general subalgoritmii, priviti dintr-o perspectiva holistica, nu fac asa ceva. Sau fac, daca ar fi necesar doar un timp foarte scurt. Insa IsSorted() are nevoie de O(n) timp, oferind un singur bit de informatie. Sub aspectul asta, funtia respectiva e de evitat, nu de pus intr-o librarie.
In cazurile absolut izolate cand ar fi nevoie de asa ceva, poti scrie functia.  Acel caz izolat ar fi si unul terminal, nu ar face parte din ceva mai complex, care sub o abordare de tip holistic ar face necesara implementarea functiei la nivel de librarie.
Mai pe scurt, IsSorted() furnizeaza un tip de informatie elementara, dar elementara pentru om, nu pentru masina. Operatiile elementare din perspectiva masinii sunt cele care furnizeaza informatii pe masura timpului pe care-l consuma.

Daca chiar ar fi necesar un IsSortted(), poate ca ar trebui o structura derivata din List<> care sa mai contina un camp care sa fie updatat la fiecare introducere de date Add().
Chestie care se face de exemplu in functia Count() pe care ai atasa-o unei liste simplu inlantuita.
Ar fi utila cand numarul de apeluri IsSorted() sau Count() e suficient de mare in raport cu numarul de apeluri Add(), deoarece se muta harababura de pe IsSorted() sau Count()  pe Add() , iar chestia asta trebuie sa se justifice cumva.
In realitate, daca sa zicem ca poate folosesti Count() pe o lista simplu inlantuita, rareori folosesti IsSorted() pentru ca mutarea harababurii pe Add() sa se justifice. De fapt nici apelarea Count() pe o lista nu e o practiva buna, iar o librarie nu ar trebui sa includa asa ceva.
Poti insa deriva tu un tip, plecand de la altul din librarie care sa inglobeze functionalitatea, dar nu-i bine sa strici libraria pentru o utilizare incorecta din perspectiva holistica.

Edited by maccip, 24 May 2022 - 11:33.


#15
parabellum

parabellum

    Senior Member

  • Grup: Senior Members
  • Posts: 2,056
  • Înscris: 06.01.2010

Quote

funtia respectiva e de evitat, nu de pus intr-o librarie.
Sa nu uiti sa le spui asta si alora responsabili cu stl-ul c++. A nu se uita ca algoritmul poate fi rulat si cu 'parallel policy', ceea ce deja nu mai e trivial pentru cineva care gaseste o bucla 'for' ca fiind dificila.

Un singur bit de informatie e adesea suficient ca sa realizezi ca gigel a dat inapoi contorul de apa sau ca cine stie ce valoare 'meter' s-a dat 'peste cap'.

Iar uneori acel contor nu permite cine stie ce 'cantitate posibil uriasa' de date, putand fi de exemplu pe 8 biti. Caz concret, chiar am intalnit asemenea contoare in pachete de retea IoT, iar o varianta in care se pierdea ordinea putea insemna de exemplu ca 's-a dat peste cap', sau mai rau, o incercare de https://en.wikipedia...i/Replay_attack (exista astfel de contoare si in protocoalele 'uzuale' de retea, dar acolo pierderea ordinii poate fi datorata rutarii diferite, de exemplu).

Edited by parabellum, 24 May 2022 - 13:43.


#16
radu103

radu103

    Senior Member

  • Grup: Senior Members
  • Posts: 7,482
  • Înscris: 15.11.2003

 maccip, on 24 mai 2022 - 10:48, said:

Sort() dureaza O(n log(n)) iar IsSort() dureaza doar O(n).
Nesemnificativ la cate elemente se iau in memorie si procesoarele de azi.
Daca lista e prea mare deja trebuie sortata pe sursa de date, in speta la db level

Edited by radu103, 24 May 2022 - 14:44.


#17
maccip

maccip

    44 ani

  • Grup: Senior Members
  • Posts: 29,005
  • Înscris: 06.01.2007
Nesemnificativ?
Cu cat ai mai multe elemente in lista, cu atat e mai semnificativ. Iar procesorul nu poate schimba clasa de complexistate a algoritmului.

Pentru suficient de multe elemente, un algoritm bun pe un abac e mai rapid decat un calculator mainframe de ultima ora intins pe un hectar pe care ruleaza un algoritm de clasa inferioara de complexitate.


Werever, acel numar va fi foarte mare, dar ideea e ca exista.

Si cel mai important e ca programator sa te obisnuiesti sa folosesti algoritmul adecvat in ceea ce priveste viteza si complexitatea, mai ales la "taskuri  generice" care pot fi scalate foarte mult.

View Postparabellum, on 24 mai 2022 - 13:40, said:

Sa nu uiti sa le spui asta si alora responsabili cu stl-ul c++.
Daca nu uiti sa le zici alora responsabili cu C#-ul, nu uit nici eu.
eu am argumentat "de ce nu", tu "de ce da". De aia nu-ti iese bine la parsing.

#18
parabellum

parabellum

    Senior Member

  • Grup: Senior Members
  • Posts: 2,056
  • Înscris: 06.01.2010

Quote

eu am argumentat "de ce nu", tu "de ce da". De aia nu-ti iese bine la parsing.
Problema e ca argumentatia ta nu prea rezista, o implementare daca chiar necesita si pozitia unde se descopera dezordinea, poate returna un iterator, de exemplu.

Quote

Pentru suficient de multe elemente, un algoritm bun pe un abac e mai rapid decat un calculator mainframe de ultima ora intins pe un hectar pe care ruleaza un algoritm de clasa inferioara de complexitate.
Cat am auzit eu povestile astea cu 'suficient de rapide', 'suficienta memorie', etc.

Pentru unele chestii chiar si memorie si viteza infinite sunt insuficiente :)

Edited by parabellum, 24 May 2022 - 16:07.


Anunturi

Second Opinion Second Opinion

Folosind serviciul second opinion ne puteți trimite RMN-uri, CT -uri, angiografii, fișiere .pdf, documente medicale.

Astfel vă vom putea da o opinie neurochirurgicală, fără ca aceasta să poată înlocui un consult de specialitate. Răspunsurile vor fi date prin e-mail în cel mai scurt timp posibil (de obicei în mai putin de 24 de ore, dar nu mai mult de 48 de ore). Second opinion – Neurohope este un serviciu gratuit.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate