Givet denna kod:

List<int> list = new List<int>() { 3, 1, 4, 2 };

var query = from number in list
where number < 3
select number;

På vilket sätt sker urvalet?

Är det först bubble sort och sen linjär sökning eller .. ? :)

du kan släppa bubble sort, stryk det ur ordlistan..

bubble sort är den enklaste form av sortering som man lär elever andra vecka på programmeringskurser.
den har inget med verkligheten att göra.

Hur som.

Linq kan anpassas att gå mot olika källor där man själv kan skriva "tolken"
så det vore möjligt att göra en egen tolk som gör olika optimeringar

Jag antar att du menar att den borde sortera först för att då slippa jämföra efter att ha hittat 2an.
Vid första anblicken så kanske det ser ut att vara en optimering att först sortera och sedan sluta söka när man hittat 2an.
Men eftersom en sortering _alltid_ är mer än 1 pass , så är en ren linjär sökning effektivare.
en sökning är 1pass , en sortering är alltid mer än så..

Jepp Linjär som Roger skriver.

Din fråga blir lite som att skriva:

List<int> list = new List<int>() { 3, 1, 4, 2 };

List<int> newList = new List<int>();
foreach(int x in list)
{
if(x < 3)
newList.Ass(x);
}

return (newList );

Dessutom kan inte LINQ veta när den träffar 2:an att det faktiskt är stopp där. Den kommer att jämföra allhop därför att den inte är optimerad för att ställa frågor mot integers utan skall kunna ställa frågan mot alla typer av data.

Har den inte specialiseringar med avseende på datatyp?!

>bubble sort är den enklaste form av sortering som man lär elever andra vecka på programmeringskurser.
>den har inget med verkligheten att göra.

Vilken verklighet lever du i?

Varje sorteringsalgoritm har sina fördelar och nackdelar.

Bubblesort kräver ingen startupkod och inget extra minne. Är därför mycket lämpad för små datamängder. Så här säger till exempel Electronic Arts

"bubble_sort has curiously been shown in practice to be a good sort for very small element counts (<5), and so it is retained for both practical and instructional purposes, though insertion_sort also works well for small sizes."

Ja det är väl en verklighet där man inte har behov av att sortera mindre än 5 element och ingen bryr sig om man slösar 5*itemsize bytes med minne..

Den verkligheten...

att den skiljer sig mot EA's lågnivå assemblerhackande spel koders må så vara..

Du är välkommen att slå dig trött ;-)

"Har den inte specialiseringar med avseende på datatyp?!"
nej,

inte mer än ngn generisk annan metod i .NET skulle kunna tänkas ha.

Metoden som where expanderar till ser ut så här:

Where<T>(Func<T, bool> func).

När du gör:

var query = from item in list
where i > 5
select i;

så kommer kompilatorn att skapa en metod som har ett lustigt namn och ser ut ungefär så här:

bool <>__func1(int item) {
return item > 5;
}

och queryn blir:

var query = list.Where(<>__func1);

Den kommer sedan exekveras inne i where funktionen för att hitta rätt. Som Roger sagt innan så blir den här översättningen annorlunda baserat på vilken backing end vi pratar om, exemplet ovan är från in memory filtrering.

När det gäller sortering så bygger den på att det du vill sortera på har ngn form av implementation av IComparable och så vitt jag vet är det en sorteringsalgoritm som .NET använder och det är inte bubblesort.

Alltså, notera att jag inte kan .NET öht. Men kan man inte göra specialiseringar med avseende på vad man template:ar?

Electronic Arts... Mins Amiga tiden som igår :-) När de kom med Deluxe Paint m.m.
Det är viss skillnad på ex Drivare vs OO kod.

Där en drivare skall gå så fort det bara går för det är så nära maskinkod som möjligt. Io M.
OO så är vi inte lika snälla, pga chatty m.m. Men du väcker en intressant tanke.

DÅ Linq kör med bla IEnumerble och ittererar från start till slut så finns det inget som kan säga åt just Queryn att sluta exekveras efter en specifik regel. Precis som Patrik säger.

Men det hade faktiskt vart rätt tufft att säga...
Du är sorterad sluta när du når siffra 3 för efter 3 kommer 4a och då är jag klar... För spara prestanda...

Mvh Johan

>att den skiljer sig mot EA's lågnivå assemblerhackande spel koders må så vara..

Det finns säkert massor av sådana på EA men kommentaren om bubble sort kom faktiskt från EA:s STL implementering. Templates med iteratorer och binära funktionsobjekt kan väl knappast kallas lågnivå.

>Alltså, notera att jag inte kan .NET öht. Men kan man inte göra specialiseringar med avseende på vad
>man template:ar?

I .Net har man generics och inte templates. Det är ganska stora skillnader och den största är att generics instantieras runtime. Överlagring är knepigt nog för kompilatorer, tänk då om man skulle försöka sig på det runtime.

"Alltså, notera att jag inte kan .NET öht. Men kan man inte göra specialiseringar med avseende på vad man template:ar?"
Nej inte direkt. Varje template (generic) är väldigt statisk och som nämnts innan är det ett runtime trick inte ett compile time trick. Självklart kan du ju göra en

if ( T is int )

men det skalar inte och är inte genersikt och LINQ använder det inte utan försöker vara så generellt som möjligt.

"Men det hade faktiskt vart rätt tufft att säga...
Du är sorterad sluta när du når siffra 3 för efter 3 kommer 4a och då är jag klar... För spara prestanda..."

Ja men är du säker på att du spara någon prestanda?

Säg att du har en osorterade lista mellan 0 och 10000 och du vill plocka ut alla värden under 9999. I ditt fall så skall du först sortera listan och sedan plocka ut 9999 poster. Utan sortering så skall du bara plocka ut 9999 poster. :)

Så det man vinner på karusellerna förlorar man på gungerna. Ibland hade man vunnit på att sortera och sedan avsluta vid rätt punkt, i andra tillfällen så förlorar man på att först sortera och sedan avsluta vid rätt punkt.

- M

Jepp det är det jag sa redan från början

En sortering är alltid mer än 1 pass.
En sökning är bara 1 pass.

Alltså så förlorar man på att sortera..

<b>>Varje template (generic) är väldigt statisk och som nämnts innan är det ett runtime trick inte ett compile time trick.</b>
Ok. Jag tänkte på att man i C++ kan göra specialiseringar eftersom templates där ligger på kompileringsnivå. Synd, det kan ju ge väsentliga vinster.

Vad gäller det andra är det klart att man i princip kan tjäna på utsökningarna om du kan göra sorteringen i ett icke tidskritiskt läge, men sen söka i ett tidskritiskt läge. I LISP eller Haskell hade man nog kunnat göra det ganska stiligt genom att kontinuerligt hålla reda på när grejer är sorterade. Alltså utan "tillägg av bool och tester", utan att det sker automatiskt.

>En sortering är alltid mer än 1 pass.
>En sökning är bara 1 pass.

>Alltså så förlorar man på att sortera..

Ja, om man bara ska göra en sökning

Nja...

Jag syfta dock på att man redan sagt åt Linq att nu är jag sorterad så Linq vet att aaahaaa nu är jag klar för jag vart sorterad...

Men nu lekte jag bara med tanken... Och så här är ju inte fallet, men vem vet Linq är nytt och än omoget på marknaden och fler stöd kommer bergis att anlända i nästa version o näste efter den.

Skall i alla fall bli kul att följa utvecklingen...

Mvh Johan