Paste: some experiments

Author: randy7
Mode: factor
Date: Wed, 4 Feb 2009 18:19:55
Plain Text | 
: overlap? ( array array -- ? ) ! { from to }
    2dup [ second ] [ first ] bi* > 
    [ 
       [ first ] [ second ] bi* >= [ f ] [ t ] if 
    ] [ 2drop f ] if ; inline
    
: spaces ( seq seq -- seq ? )
    2dup [ overlap? ] curry map sift empty?
    [ suffix t ] [ drop f ] if ;
    
: spaces2 ( seq seq -- seq )
    2dup [ overlap? ] curry map sift empty?
    [ suffix ] [ "overlap" write nl  drop ] if ;   
    
: non-overlaps ( seq -- seq )
    { } [ spaces2 ] reduce ;
    


: (overlaps?) ( seqs seq -- ? )
    [ overlap? ] curry find 2array { f f } = not ;
 
: seq-overlaps? ( seq -- ? )
    dup empty? [ drop f ] [
        [ rest ] [ 1 head first ] bi
        2dup (overlaps?) [ 2drop t ] [ drop seq-overlaps? ] if
    ] if ; recursive
    

    
    
    { { 1 2 } { 2 3 } { 5 8 } { 4 6 } { 10 12 } } 7000000 { 14 18 } <array> append
    [ seq-overlaps? ] curry time
    ! 6.234375 seconds
    ! tried rest-slice but it didn't make much difference.
    ! why is it linear when find in (overlaps?) should stop at the fourth item ?
    
    ! in other words: shouldn't it be equal to 
    { { 1 2 } { 2 3 } { 5 8 } { 4 6 } { 10 12 } } 
    [ seq-overlaps? ] curry time

Annotation: shorter, more efficient version

Author: LittleDan
Mode: factor
Date: Wed, 4 Feb 2009 18:44:01
Plain Text | 
: overlaps? ( seq -- ? ) 
    [ [ first ] compare ] sort
    2 <clumps> [ first2 [ second ] [ first ] bi* < ] all? not ;

Annotation: This is what I originally wanted

Author: randy7
Mode: factor
Date: Thu, 5 Feb 2009 23:06:48
Plain Text | 
SYMBOL: vikky V{ } vikky set

: seq-overlaps? ( seq -- ? )
    [ rest-slice ] [ 1 head first ] bi ! rest head
    [ vikky get ] dip 2dup (overlaps?) ! rest vikky head t/f
        [ 3drop t ] [ 
        suffix  
        vikky set     ! rest
        seq-overlaps? 
        ] if ;

Annotation: to prove the point

Author: randy7
Mode: factor
Date: Thu, 5 Feb 2009 23:10:20
Plain Text | 
( scratchpad ) { { 1 2 } { 2 3 } { 5 8 } { 4 6 } { 10 12 } } 7000000 { 14 18 } <array> append
    [ seq-overlaps? . ] curry time
t
==== RUNNING TIME

0.0 seconds

! the mistake was that find was indeed stopping at the fourth item, but until that item, it was matching against all of the huge 'rest'. compares 1 to rest, 2 to rest, etc.
! so now, I only use find on the short list of accumulated heads, which was what I actually meant to do.

New Annotation

Summary:
Author:
Mode:
Body: