Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (684)
Games in Android Showcase (196)
games submitted by our members
Games in WIP (752)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Memoizing positions  (Read 665 times)
0 Members and 1 Guest are viewing this topic.
Offline i30817

Junior Devvie

« Posted 2012-06-23 18:43:18 »

I've got this... iterator class. It's type doesn't really matter (it's a document find iterator)

Anyway, it's logic is implemented using hasNext() as the code that actually calculates the new index... and it's hasPrevious() is:
    public boolean hasPrevious() {
        [...already done at least once logic...]
        //lame O(n) backward search
        //TODO please memoize this
        int localIndex = searchIndex;
        searchIndex = 0;
        int tmp, tmp2 = -1;

        while (hasNext()) {
            tmp = next();
            if ((tmp + 1) < localIndex) {
                tmp2 = tmp;
            } else {

        if (tmp2 == -1) {
            //revert the index if found nothing.
            searchIndex = localIndex;
            return false;
        } else {
            //prepare for previous (next() clobbered lastFoundLocation)
            lastFound = tmp2;
            return true;

 persecutioncomplex (so embarrassed)

Anyway since the underlying search algorithms don't support backwards searching, memoization is the obvious answer to this problem, although it would introduce stale cache issues.
I don't have much experience with memoization - what do you think it's the best policy: to expand the table (much harder it looks like) or just null it and let it be reconstructed from scratch?
Offline jonjava
« Reply #1 - Posted 2012-06-24 23:17:16 »

What do you mean by "memorizing this"? Saving it to file?

Offline i30817

Junior Devvie

« Reply #2 - Posted 2012-06-25 02:47:24 »

Memory. Save the preprocessed hits to memory

it's a waste of processing cycles - each 'has previous' is actually recalculating the hits of the search phrase in the whole text prior to the current index (and having a cache may actually help in hasnext too).

What is making me hesitate is that i hate and fear caches because of the complexity introduced in maintaining them:
The document may change, the search index may change, the search phrase may change, actually finding the cache index. Of these, only the first two look amenable to retaining part of the cached search, haven't really thought about it more than this, it makes me so mad about this inelegance, oh why didn't you make a backwards search variant mr moore, oh why do i have to deal with caching behaviour anyway for better performance ffgfgdgufgfgdgfdgdfjdkgdjfjgdjk.
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

orrenravid (240 views)
2016-07-16 03:57:23

theagentd (310 views)
2016-07-11 14:28:54

Hydroque (395 views)
2016-07-06 05:56:57

Hydroque (554 views)
2016-07-03 08:52:54

GrandCastle (416 views)
2016-07-01 09:13:47

GrandCastle (409 views)
2016-07-01 09:09:45

CopyableCougar4 (463 views)
2016-06-25 16:56:52

Hydroque (432 views)
2016-06-22 02:17:53

SwampChicken (396 views)
2016-06-20 13:22:57

SwampChicken (308 views)
2016-06-20 13:22:49
Making a Dynamic Plugin System
by Hydroque
2016-06-25 00:13:25

Java Data structures
by BinaryMonkL
2016-06-13 21:22:09

Java Data structures
by BinaryMonkL
2016-06-13 21:20:42

FPS Camera Tutorial
by Hydroque
2016-05-22 05:40:58

Website offering 3D Models specifically for games for free
by vusman
2016-05-18 17:23:09

Website offering 3D Models specifically for games for free
by vusman
2016-05-09 08:50:56

Website offering 3D Models specifically for games for free
by vusman
2016-05-06 11:10:21

Website offering 3D Models specifically for games for free
by vusman
2016-04-29 12:56:17 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!