Ik heb voor mijn aankliksysteem van rechthoeken en andere vormen (dit zijn dan voor de 1e test rechthoeken) een snel zoek systeem nodig.
De opslag van de 4 coordinaten moet vanaf -32768 tot/met 32767 zijn (smallint in pascal)
Het wegschrijven moet ook snel kunnen gebeuren.
Er is ook nog een level test en een aan/uit.
Wie heeft tips.
Ook zoek ik wat technieken om andere vormen snel te kunnen verwerken.
Laatste berichten
-
22:08
wig 11
-
21:37
speciale rel. theorie 12
-
21:22
[scheikunde] vraag Chemie - wat is de oplossing? 11
-
20:14
Aardlek-schakelaar 2
-
15:56
Programmeren met vectoren 6
-
14:53
Straatklok loopt 5 minuten voor 12
-
25 apr
Gravity and gravitation 4
-
25 apr
Bruine vlekken op treinaanwijzerbord 10
-
25 apr
Vogels in de stad zijn goede klussers 2
-
25 apr
Rood laserlicht 3
-
25 apr
Herleiden afmetingen vanaf een foto 21
-
25 apr
[wiskunde] Prijs Product per KG; Alternatief Inzicht 3
-
25 apr
do-re-mi-fa-so vliegtuigen 9
-
25 apr
geen minkowski-ruimte toch? Doe ik dit nou fout? 17
-
25 apr
[natuurkunde] kroon van koning op Syracuse 10
-
25 apr
2013 – Augustus Vraag 3 3
-
24 apr
Vraag 2009 Juli Vraag 5 5
-
24 apr
positie 2
-
24 apr
Schroefdraad berekening 8
-
24 apr
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Sneller zoeken naar rechthoeken
-
- Berichten: 691
Sneller zoeken naar rechthoeken
Een computertaal is voor mensen, niet voor de computer.
-
- Berichten: 2.746
Re: Sneller zoeken naar rechthoeken
Dus je moet onderzoeken of 4 coordinaten een rechthoek voorstelt? En ligt de rechthoek evenwijdig met de coordinaatassen?
-
- Berichten: 829
Re: Sneller zoeken naar rechthoeken
nee ik denk dat hij bedoelt dat je een coördinaat meegeeft en het algo in een lijstje moet gaan zoeken naar rechthoeken die de coördinaat bevatten.
Maar hoe snel wil je dat je agoritme gaat
ik denk dat je beter een ordening in je rechthoeken stopt op linker-boven-hoek-punt (kan je coderen als een integer door. Daarmee zou je al heel wat rechthoeken heel snel kunnen wegfilteren (die bijvoorbeeld onder of rechts van je punt beginnen) met behulp van binair zoeken. Maar de complexiteit kan je volgens mij niet naar
EDIT: Dit is dan ook goed uitbreidbaar naar andere vormen, als je gewoon het minimum van de x, en y waarden gebruikt om je vormen te ordenen, wel blijf je werken in
Maar hoe snel wil je dat je agoritme gaat
\(O(n)\)
is zonder twijfel mogelijk, maar ik begrijp dat dat mss niet snel genoeg isik denk dat je beter een ordening in je rechthoeken stopt op linker-boven-hoek-punt (kan je coderen als een integer door
Code: Selecteer alles
x<<15|y\(O(\log(n))\)
brengen, omdat je met een dubbele variabele werkt.EDIT: Dit is dan ook goed uitbreidbaar naar andere vormen, als je gewoon het minimum van de x, en y waarden gebruikt om je vormen te ordenen, wel blijf je werken in
\(O(n)\)
als worst-case (overlappende rechthoeken dus of rechthoeken die links-boven ervan beginnen). Je zou ook een tweede lijst kunnen maken met het rechts-beneden-hoek-punt. En op die manier een interval kunnen afbakenen, als je ongeveer begrijpt wat ik bedoel."Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
-
- Berichten: 829
Re: Sneller zoeken naar rechthoeken
er is een klein foutje in mn code geslopen dat moet natuurlijk
zijn die verhoging is niet altijd nodig, het hangt af van de taal die je hiervoor gebruikt.
Code: Selecteer alles
(x+32768)<<16|(y+32768)"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)
--Vladimir Lenin-- (Владимир Ильич Ульянов)
-
- Berichten: 6.905
Re: Sneller zoeken naar rechthoeken
Bedoel je een algoritme om te detecteren of het een rechthoek is of een algoritme om te zien of een gegeven punt in de rechthoek ligt. (In het laatste geval is het probleem verwant met projecteuler probleem 102 waarvoor er verschillende elegante oplossingen zijn)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
-
- Berichten: 691
Re: Sneller zoeken naar rechthoeken
Nu heb ik de volgende opzet:
De aanklik elementen zijn in groepen verdeelt.
Een groep kan men in 1 keer aan en uit zetten.
De zoeker loopt alle groepen af die aan staan.
Op het groepgeheugen staat een lijst van adressen van zijn klikelementen.
Een 0 is een gewist klikelement.
Een klikelement zelf heeft ook een aan/uit (een byte : 0 is uit)
Het klikelement heeft nog een level.
Het klikelement omvat wel het adres van de groep maar niet de plek op de groep.
Het wissen van losse klikelementen is niet 123 aan de orde.
Het wissen van een groep moet snel gaan.
Het aanmaken van de klikelementen ook.
En als het level gelijk is komen diegene op de groep lijst die later komen als winnaar uit de bus.
Ik heb al wat snelheidswinst kunnen boeken met het volgende:
de test voor off/on en level en oproep van een testroutine na de test van de coordinatie in plaats van ervoor.
De test was eerst 121 seconden en met de coordinatie ervoor was 44 seconden.
(4000000 keer getest met 1000 elementen van 30 bij 30)
Ook heb ik gemerkt dat het gebruik van een buffer variabele om 4 coordinaten van het geheugen te halen langzamer werkt dan 4 keer direkt het geheugen te benaderen.
Ook het gebruik van een lokale i.p.v. een globale gaf 25% tijdwinst.
(de lokale wordt wel een globale bij de oproep naar de routine)
Waar ik aan zit te denken is om het scherm in zeg 100 blokken te verdelen.
Indien het element in zijn geheel in zo'n blok past bekomt het een zoekcode (het blok waarin het pastte).
Indien het element niet past dan hebben we zoekcode 0.
De aanklik elementen zijn in groepen verdeelt.
Een groep kan men in 1 keer aan en uit zetten.
De zoeker loopt alle groepen af die aan staan.
Op het groepgeheugen staat een lijst van adressen van zijn klikelementen.
Een 0 is een gewist klikelement.
Een klikelement zelf heeft ook een aan/uit (een byte : 0 is uit)
Het klikelement heeft nog een level.
Het klikelement omvat wel het adres van de groep maar niet de plek op de groep.
Het wissen van losse klikelementen is niet 123 aan de orde.
Het wissen van een groep moet snel gaan.
Het aanmaken van de klikelementen ook.
En als het level gelijk is komen diegene op de groep lijst die later komen als winnaar uit de bus.
Ik heb al wat snelheidswinst kunnen boeken met het volgende:
de test voor off/on en level en oproep van een testroutine na de test van de coordinatie in plaats van ervoor.
De test was eerst 121 seconden en met de coordinatie ervoor was 44 seconden.
(4000000 keer getest met 1000 elementen van 30 bij 30)
Ook heb ik gemerkt dat het gebruik van een buffer variabele om 4 coordinaten van het geheugen te halen langzamer werkt dan 4 keer direkt het geheugen te benaderen.
Ook het gebruik van een lokale i.p.v. een globale gaf 25% tijdwinst.
(de lokale wordt wel een globale bij de oproep naar de routine)
Waar ik aan zit te denken is om het scherm in zeg 100 blokken te verdelen.
Indien het element in zijn geheel in zo'n blok past bekomt het een zoekcode (het blok waarin het pastte).
Indien het element niet past dan hebben we zoekcode 0.
Een computertaal is voor mensen, niet voor de computer.
-
- Berichten: 5.609
Re: Sneller zoeken naar rechthoeken
Ik weet niet hoe het met de anderen zit, maar hier kan ik helaas niks van maken, en al helemaal niet met betrekking tot je vraag.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
-
- Berichten: 6.905
Re: Sneller zoeken naar rechthoeken
Zelfde hier. Maak eens een mooie probleemstelling :eusa_whistle:
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.
