Algoritm: Hitta uteblivna heltal i en sekvens

Citera flera Citera

2013-07-17 17:05

Xaanin

Medlem

Plats: Täby
Registrerad: Aug 2001

●

Givet att du sorterat din array så vet du att om två element ligger bredvid varandra så ska dessa två element också vara på varandra följande heltal. Är så inte fallet så saknas alla heltal som ligger mellan dessa två element.

Det är även tänkbart att göra en variant på counting sort som räknar förekomsten av alla element, men istället för att sedan sortera dem skriva ut de element som förekom 0 ggr.

Citera flera Citera

2013-07-17 17:16

Lisianthus

Medlem

Plats: Uppsala
Registrerad: Dec 2008

●

Det jag skulle göra är någon form av lista som har alla nummer mallan A och B (Intervallet) och sedan gå igenom listan på tal som vi har och pricka av dem en och en. Sedan inverera listan, alla om inte är avprickade saknas.

Gör ju att listan behöver itereras endast en gång, sedan behövs den inte sorteras heller.
Ifall du väldigt gärna vill kan jag skriva en kort exempelkod.

Visa signatur

Denon AVR-1801 | Dali Blue 5005 | Turtle Beach Audio Advantage Micro II

Citera flera Citera

2013-07-17 17:22

Otsu

Medlem

Plats: 127.0.0.1
Registrerad: Apr 2005

●

får ni använda dynamiska datastrukturer? Verkar dumt att använda vektorer men det kanske är en del av uppgiften.

Min lösning är en metod som använder ArrayList med heltal som input, samt de största och minsta talen (det verkar som du känner till dem).

Att knuffa in en ArrayList i ett HashSet går på O(n) operationer. Sen måste vi iterera över hela tallinjen som våra m värden spänner upp, detta är O(m) operationer. För varje tal på vår tallinje måste vi göra ett uppslag i vårt hashset, men det går på O(1). Alltså kommer det gå väldigt snabbt, men de dynamiska datastrukturerna tar ev lite mer minne än enkla arrays.

ArrayList<Integer> foo(ArrayList<Integer> list, int smallestInt, int largestInteger) {
	HashSet<Integer> set = new HashSet<Integer>();
	set.addAll(list);
	ArrayList<Integer> missingInts = new ArrayList<Integer>();
	
	for(int i = smallestInt; i <= largestInteger; i++)
		if(!set.contains(i))
			missingInts.add(i);
	
	return missingInts;
}

Citera flera Citera

2013-07-17 17:24

jeebus

Medlem

Plats: ekerö
Registrerad: Nov 2009

●

Skrivet av Lisianthus:

Det jag skulle göra är någon form av lista som har alla nummer mallan A och B (Intervallet) och sedan gå igenom listan på tal som vi har och pricka av dem en och en. Sedan inverera listan, alla om inte är avprickade saknas.

Gör ju att listan behöver itereras endast en gång, sedan behövs den inte sorteras heller.
Ifall du väldigt gärna vill kan jag skriva en kort exempelkod.

Dold text

Ja gärna, behöver inte va nått fungerande bara så jag greppar hur du tänker.
Om du har tid och ork dvs

Visa signatur

Citera flera Citera

2013-07-17 17:40

jeebus

Medlem

Plats: ekerö
Registrerad: Nov 2009

●

Skrivet av Otsu:

får ni använda dynamiska datastrukturer? Verkar dumt att använda vektorer men det kanske är en del av uppgiften.

Min lösning är en metod som använder ArrayList med heltal som input, samt de största och minsta talen (det verkar som du känner till dem).

Att knuffa in en ArrayList i ett HashSet går på O(n) operationer. Sen måste vi iterera över hela tallinjen som våra m värden spänner upp, detta är O(m) operationer. För varje tal på vår tallinje måste vi göra ett uppslag i vårt hashset, men det går på O(1). Alltså kommer det gå väldigt snabbt, men de dynamiska datastrukturerna tar ev lite mer minne än enkla arrays.

ArrayList<Integer> foo(ArrayList<Integer> list, int smallestInt, int largestInteger) {
	HashSet<Integer> set = new HashSet<Integer>();
	set.addAll(list);
	ArrayList<Integer> missingInts = new ArrayList<Integer>();
	
	for(int i = smallestInt; i <= largestInteger; i++)
		if(!set.contains(i))
			missingInts.add(i);
	
	return missingInts;
}

Uppgiften är att vi ska göra klasser för: dynamic array, binary search tree och linked list. Sen algoritmen är för att testa klasserna i princip.

Står ingenting i uppgiftsbeskrivningen om vad vi får använda när det kmr till algoritmen, så det är nog cool.
På tal om hastighet/minnesanvänding så har jag ingen aning om vad O(1) betyder och stör mig som fan på det eftersom man stöter på sådana beskrivningar lite här och var. Vart lär man sig sånt? inget vi fått lära oss tyvär.

Visa signatur

Citera flera Citera

2013-07-17 18:09

MrSir

Medlem

Registrerad: Jul 2013

●

Nu är jag förvirrad. Vilket programmeringsspråk använder du?
Sedan, om ni ska göra olika klasser för att testa algoritmen måste man väl veta hur dom klasserna ser ut? Dom kanske ska ha vissa funktioner som alla är likadana? Typ .append .at .erase?

Sen kan man ju fråga sig hur algoritmen ska kunna använda tre olika klasser. Antigen måste algoritmen använda templates eller så får du använda någon typ av casting?

edit: Får ni betyg efter hur snabb algoritmen är eller?

Citera flera Citera

2013-07-17 18:46

jeebus

Medlem

Plats: ekerö
Registrerad: Nov 2009

●

Skrivet av MrSir:

Nu är jag förvirrad. Vilket programmeringsspråk använder du?
Sedan, om ni ska göra olika klasser för att testa algoritmen måste man väl veta hur dom klasserna ser ut? Dom kanske ska ha vissa funktioner som alla är likadana? Typ .append .at .erase?

Sen kan man ju fråga sig hur algoritmen ska kunna använda tre olika klasser. Antigen måste algoritmen använda templates eller så får du använda någon typ av casting?

edit: Får ni betyg efter hur snabb algoritmen är eller?

Oj förlåt om jag jag var oklar vid beskrivningen :/
Språket är c++. Är klar med klasserna så därför skrev jag inget om dom.
Exakt såhär lyder uppgiften kring algoritmen

The procedure is the same for all three container classes:
- Start a timer
- Traverse the
RandomArray
and insert all values into the container
- Find all values that are missing between 1 and 1 000 000 by traversing the container
- If a number is missing, insert it into the
MissingArray
- Stop timer

Dold text

Och nej klasserna är inte exakt likadana, så kmr förmodligen få skriva 3 versioner av samma algoritm (små ändringar bara).
Tror betyget sätts efter hurvida man förstår för/nackdelar med olika containers.

Visa signatur

Citera flera Citera

2013-07-17 19:08

MrSir

Medlem

Registrerad: Jul 2013

●

// ###
int DERP = (-2^16)+1;
vector<int> List; // Fyll med random heltal
vector<int> Full;
for(int i = 0; i < 1000)
{
Full.append(i);
}
for(int i = 0; i < List.size(); i++)
{
Full.at(List.at(i)) = DERP;
}
for(int i = Full.size() - 1; i > -1; i--)
{
if(Full.at(i) == DERP)
Full.erase(Full.begin() + i);
}
//
//
//

Dold text

Samma som Otsu gjorde fast utan Javaklasser. Kanske kan va nått.

Citera flera Citera

2013-07-17 21:01

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Lösning som använder standardbiblioteket, närmare bestämt set_difference() från algorithm C++ för att lösa detta problem. Tar ca 1s att köra för 1M element på en icke överklockad Raspberry Pi när den både genererar en sekvens [1..1M] där viss tal saknas och räknar ut en sekvens där de tal som saknas finns med. På en 2010 år MBP (Core i5 520 @ 2.4GHz) tar det runt 0.1s.

"Tricket" är att köra set_difference() på alla tal från [1..1M] med den sekvens där vissa tal saknas, de tal som inte tas bort ur sekvensen med alla tal är ju de som saknas i den andra sekvensen, detta ger en tidskomplexitet på O(N)

Så "lösningen" på problem i detta program är implementationen av inverse(), resten är bara för att spänna upp problemet.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> numbers;

const unsigned MAX_NUM = 1000000;

// Skapa en vector med alla tal [1..MAX_NUM]                           
numbers
range()
{
    numbers v(MAX_NUM);

    for (int i = 0; i < MAX_NUM; i++)
        v[i] = i + 1;

    return v;
}


// Skapa en (sorterat) mängd med tal från [1..MAX_NUM] där vissa tal   
// (slumpmässigt) tagits bort                                          
numbers
gen_numbers()
{
    int keep = rand() % MAX_NUM;
    numbers v = range();

    random_shuffle(v.begin(), v.end());
    v.erase(v.end() - (MAX_NUM - keep), v.end());
    sort(v.begin(), v.end());

    return v;
}

// Skapa inversen av 'nums', i.e. on MAX_NUM är 5 och 'nums' är        
// [ 1 4 5 ] så får man [ 2 3 ] i svar.                                
numbers
inverse(const numbers& nums)
{
    numbers r = range();
    numbers inverse(MAX_NUM);
    numbers::iterator last_missing;

    last_missing = set_difference(r.begin(), r.end(),
                                  nums.begin(), nums.end(),
                                  inverse.begin());
    // Minska storleken på 'inverse' till de element som är skillnaden
    // mellan alla element 'r' och de element som skickades in som     
    // argument 'nums'                                                 
    inverse.erase(last_missing, inverse.end());
    return inverse;
}

int
main()
{
    srand(time(NULL));
    numbers nums = gen_numbers();

    cout << "Numbers " << nums.size() << endl;
    // for (numbers::iterator it = nums.begin(); it != nums.end(); ++it)         
    //     cout << *it << endl;                                                  

    numbers missing = inverse(nums);
    cout << "Missing " << missing.size() << endl;
    // for (numbers::iterator it = missing.begin(); it != missing.end(); ++it)   
    //     cout << *it << endl;                                                  

}

Dold text

Edit: Missade att du inte har koll på vad O(N) betyder, såg bara att andra använt uttrycket så trodde det var uppenbart.

O(N) betyder att den genomsnittliga tiden det tar att köra algoritmen är linjär proportionellt mot hur många element man har, d.v.s om det tar 5 sekunder att hantera 100.000 element så kommer det ta ungefär 10 sekunder att hantera 200.000 element.
O(1) betyder att den genomsnittliga tiden att köra algoritmen är oberoende av antal element
O(N^2) betyder att genomsnittliga tiden växer kvadratiskt med antal element.

Ofta är man bara intresserad av den genomsnittliga tiden, men ibland kan det vara viktigt att även veta den värsta tidskomplexiteten. I ett exempel ovan används en hash-tabell, att hitta ett element i en sådan är O(1) i genomsnitt men i värsta fall tar O(N)! Balanserade binärträd bar både en genomsnittlig och en worst-case komplexitet som är O(log(N)), så om worst-case är viktigt är det bättre att använda ett sådant träd än en hash-tabell.

set_difference() har en medel och värsta komplexitet som båda är O(N) där N är storleken på det man tar bort.

Senast redigerat 2013-07-17 21:25

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Citera flera Citera (1)

2013-07-17 21:48

MrSir

Medlem

Registrerad: Jul 2013

●

set_difference() tar emot 5 itererare vad jag förstått. Om man har en hemgjord vektor där all data ligger på rad, räcker det då att man anger itererarna som en pekare med en datatyp av rätt Byte-längd då? Eller kör std-lib med ngt hokuspokus?

Frågan är hur man använder set_difference med ett hemsnickrat binärträd. Går det?
edit: eller en länkad lista.

Citera flera Citera

2013-07-17 22:07

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av MrSir:

set_difference() tar emot 5 itererare vad jag förstått. Om man har en hemgjord vektor där all data ligger på rad, räcker det då att man anger itererarna som en pekare med en datatyp av rätt Byte-längd då? Eller kör std-lib med ngt hokuspokus?

Frågan är hur man använder set_difference med ett hemsnickrat binärträd. Går det?
edit: eller en länkad lista.

Det går så länge som din struktur uppfyller kraven för en input iterator.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Citera flera Citera

2013-07-19 23:28

DeluxXxe

Medlem

Plats: Karlskrona
Registrerad: Feb 2007

●

Skrivet av jeebus:

Oj förlåt om jag jag var oklar vid beskrivningen :/
Språket är c++. Är klar med klasserna så därför skrev jag inget om dom.
Exakt såhär lyder uppgiften kring algoritmen

The procedure is the same for all three container classes:
- Start a timer
- Traverse the
RandomArray
and insert all values into the container
- Find all values that are missing between 1 and 1 000 000 by traversing the container
- If a number is missing, insert it into the
MissingArray
- Stop timer

Dold text

Och nej klasserna är inte exakt likadana, så kmr förmodligen få skriva 3 versioner av samma algoritm (små ändringar bara).
Tror betyget sätts efter hurvida man förstår för/nackdelar med olika containers.

Uppgiftspecsen säger ju att ni ska traversera och göra logiken själva. Annars ser detta ut att vara ett typexemplar för att lösa med delmängder (union, interscetion osv).

Illusterar detta i följande java kod:
http://pastie.org/8156777

Såg att ni använder c++, men det finns liknande funktioner att kalla på där.

Visa signatur

Phenom X6 1045T | Corsair TWIN2X PC6400C4DHX 2x2GB + Crucial Ballistix Sport 2x2GB | Gigabyte ma785gmt-us2h | Silverstone Temjin 08 | Corsair VX450

Citera flera Citera

2013-07-20 00:13

akatabrask

Medlem

Plats: Lund
Registrerad: Mar 2011

●

Du borde kunna ha en booleanarray på 100 element där du kan markera vilka tal som förekommer i din array. Sedan är det bara att gå igenom den och se vilka värden som inte finns.

Tänk bara på att om du har värden större än 100 (resp. mindre än 0) behöver du ha en större booleanarray. Så lösningen funkar inte bra om du har stor skillnad mellan största och lägsta värde.