Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (489)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (555)
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 473 times)
0 Members and 1 Guest are viewing this topic.
Offline i30817

Junior Member





« 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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
    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 {
                break;
            }
        }

        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 Member





« 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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Nickropheliac (12 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

CopyableCougar4 (27 views)
2014-08-22 19:31:30

atombrot (40 views)
2014-08-19 09:29:53

Tekkerue (38 views)
2014-08-16 06:45:27

Tekkerue (34 views)
2014-08-16 06:22:17

Tekkerue (24 views)
2014-08-16 06:20:21

Tekkerue (34 views)
2014-08-16 06:12:11

Rayexar (72 views)
2014-08-11 02:49:23

BurntPizza (47 views)
2014-08-09 21:09:32
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org 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‑gaming.org
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!