Springen naar inhoud

Sneller zoeken naar rechthoeken


  • Log in om te kunnen reageren

#1

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 31 augustus 2009 - 23:49

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.
Een computertaal is voor mensen, niet voor de computer.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

stoker

    stoker


  • >1k berichten
  • 2746 berichten
  • Ervaren gebruiker

Geplaatst op 01 september 2009 - 07:29

Dus je moet onderzoeken of 4 coordinaten een rechthoek voorstelt? En ligt de rechthoek evenwijdig met de coordinaatassen?

#3

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 01 september 2009 - 12:26

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
LaTeX is zonder twijfel mogelijk, maar ik begrijp dat dat mss niet snel genoeg is
ik denk dat je beter een ordening in je rechthoeken stopt op linker-boven-hoek-punt (kan je coderen als een integer door
x<<15|y
. 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 LaTeX 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 LaTeX 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.

Veranderd door Vladimir Lenin, 01 september 2009 - 12:30

"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)

#4

Vladimir Lenin

    Vladimir Lenin


  • >250 berichten
  • 829 berichten
  • Ervaren gebruiker

Geplaatst op 01 september 2009 - 12:44

er is een klein foutje in mn code geslopen dat moet natuurlijk
(x+32768)<<16|(y+32768)
zijn die verhoging is niet altijd nodig, het hangt af van de taal die je hiervoor gebruikt.
"Als je niet leeft zoals je denkt, zul je snel gaan denken zoals je leeft."
--Vladimir Lenin-- (Владимир Ильич Ульянов)

#5

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 01 september 2009 - 13:31

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.

#6

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 01 september 2009 - 18:13

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.
Een computertaal is voor mensen, niet voor de computer.

#7

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 01 september 2009 - 21:57

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.

Veranderd door 317070, 01 september 2009 - 21:57

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-

#8

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 02 september 2009 - 07:01

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures