AltME groups: search

That's essentially the data structure we use in the archive at REBOL.org, 
Reichart.

Works fast and has scaled so far -- with nearly 150,000 posts from 
this world:
   http://www.rebol.org/aga-groups-index.r?world=r3wp

This weekend (probably).....The 150,000th [web-public] post in this 
world:
    http://www.rebol.org/aga-groups-index.r?world=r3wp
It could be you!

Thanks Doc -- I had not noticed that Red is flagged [web-public].

Theoretically, [web-public] gets you:

....automatically published on REBOL.net (though that appears to 
no longer be updated):
       http://www.rebol.net/altweb/rebol3/index.html

....and published on REBOL.org at the discretion of the Library Team. 
       http://www.rebol.org/aga-groups-index.r?world=r3wp


As Graham suggests there may be some issues, especially as REBOL.org 
is funded by RT. I'll ask the Library team to discuss.

Restoring my website at a new location.
So far just uploaded COMLib-anton
http://rolls.anton.id.au/rebol/os/windows/COMLib/index.html

New update of RMA version of R3 host-kit is available at http://www.rm-asset.com/code/downloads/index.html

This release contains:

-TO-IMAGE fixes
-TEXT rendering related improvements and code cleanup


NOTE: This version is also needed to be able run the latest R3GUI 
from RMA.

New update of RMA version of R3 host-kit is available at http://www.rm-asset.com/code/downloads/index.html

This release contains:

-enhanced GUI-METRIC function


NOTE: This version is also needed to be able run the latest R3GUI 
from RMA.

New update of RMA version of R3 host-kit is available at http://www.rm-asset.com/code/downloads/index.html

This release contains:


-Windows: reworked keyboard events handling (key-up events support, 
ctrl+tab detection, base for ALT+key handling, etc.)
-text clipping bugfix


NOTE: This version is also needed to be able run the latest R3GUI 
from RMA.

http://www.microchip.com/en_US/family/mplabx/index.html
MicroChip came out with a crossplatform IDE (after ~10+ years)
It's in Java and 37MB zipped.
Another opportunity missed where Rebol could have excelled...

Rebol plugin: 
you can visit: http://www.maxvessi.net/rebsite/plugin/index.html

to test if it works, tha pages contain some scripts. If you want, 
I can adder more...

New update of RMA version of R3 host-kit is available at http://www.rm-asset.com/code/downloads/index.html

This release contains following changes:
-added active/inactive events
-fixed compiler warnings
-fixed modal window key events bug

-added window show states programatic handling (see SHOW command 
help)
-fixed unicode text rendering bug
-fixed memory leak in text dialect


NOTE: This version is also needed to be able run the latest R3GUI 
from RMA.

Yes. I deliberately designed it so that the index binary (which ideally 
should always be memory resident) is as small as possible and that 
the data binary only requires seek and append operations (which are 
well suited to disk access). I need to do a few more benchmarks, 
but the next release should include a "data on disk" option.

Ie I understand from documentation basic index contains offsets to 
each respective record and is coded as binary, but where are the 
indexes used for quick search on columns?

http://www.dobeash.com/RebDB/rebdb3.html#section-4.6gives a brief 
but complete idea of how indexing works. The low-level implementation 
is quite simple:


 - The index is a binary! with each n bytes (n = idx-size, defaulting 
 to 2) representing on offset into the data binary! (start of row).

 - The index is sorted by/with a number of columns (left to right) 
 equal to the number of key columns (minimum of 1).
	- Updates and inserts that break this order set a reindex flag.

 - Lookup and seek both check the reindex flag prior to searching 
 the index binary! using a binary search ( http://en.wikipedia.org/wiki/Binary_search_algorithm
 ).

 - Lookup returns a single row (where # key values = # key columns)

 - Seek uses Lookup to return a range of values (where # key values 
 <> # key columns) and then does a linear match on each row


I'll devote a bit more time/space in the documentation to flesh this 
out with examples.

Great news! thanks for upgrade. What about promissed file storage, 
i.e. is ti possible to operate the DB and index binary directly to/from 
file?

Really neat is you may create as many index columns as you need/want 
and then you can use only those ones what makes sence for you selection 
parameters. I.e. you can use multiple indexes/couners above one dataset 
and then use multiple selection for BETWEEN statement for example.

I've got only one exception. If I need different schema for each 
row (like in DevChat for example) I have to use Binary dat ecapsulation 
and sniff in binary  in second level. But multiple index columns 
helps alot in this.

Ashley I think the name Index is little bit missleading the more 
appropriate would be offsets.  Anyway real indexes (ordered lists), 
are you building them on demand each new selection? Ie it is rebuilded 
on each selection or there are not used at all and each selection 
traverses thru data one of three methods?

Or maybe make the question easier is it possible to create and save 
true index on column?

The index [of offsets] is created by reading a number of columns 
(min 1) equal to key-cols and inserting both the composite row and 
the offset into a block which is then sorted by the composite row. 
For eaxmple:


Say we have 2 columns of integers in the index and also assume we 
have two rows.

Reading:

	3 2 ...
	2 3 ..

might create an intermediate block like:

	#{0034} #{01030102}	; note the #{01} field length indicators}
	#{0056} #{01020103}

which is sorted to produce an index of:

	#{00560034}


Index is updated as rows are inserted or deleted. Some insert and 
update operations will set a reindex flag which is acted upon the 
next time a lookup or seek is performed.


This index is maintained automatically by RebDB ... you cannot "create" 
one in the traditional sense of the word. The weakness of this scheme 
is it assumes that key access is by column 1 OR column 1 & column 
2. It doesn't handle the situation where you need key access to column 
1 OR column 2 (which in my experience is a fairly uncommon case).

Anyway I'like to ask again about direct file storage of dat/index 
parts (file based database)  is it possible?

RebDB question on REBOLforum:

    http://www.rebolforum.com/index.cgi?f=printtopic&topicnumber=46

using find/skip and an index for what item to search for in the record... 
we get by FAR the fastest search... if you count the fact that generating 
the keys for find-very-fast often takes as long as the search itself, 
in dense searches.

ultimate-find below gives the results of this new function


preparing sparse data
6000005
sparse tests:
feach(): 5.4.3.2.1. -> 0:00:04.89   4 matches found
----------------
find-fast(): 5.4.3.2.1. -> 0:00:00.719   4 matches found
----------------
find-really-fast(): 5.4.3.2.1. -> 0:00:00.234   4 matches found
----------------
ultimate find(): 5.4.3.2.1. -> 0:00:00.594   4 matches found
----------------

dense match with key/value collisions
6000000
feach(): 5.4.3.2.1. -> 0:00:13.343   221606 matches found
----------------
find-fast(): 5.4.3.2.1. -> 0:00:14.813   221606 matches found
----------------

find-really-fast(): 5.4.3.2.1. -> 0:00:07.718   221606 matches found
----------------
ultimate find(): 5.4.3.2.1. -> 0:00:06.735   221606 matches found
----------------

dense match without key/value collisions
6000000
feach(): 5.4.3.2.1. -> 0:00:13.969   222405 matches found
----------------
find-fast(): 5.4.3.2.1. -> 0:00:09.812   222405 matches found
----------------

find-really-fast(): 5.4.3.2.1. -> 0:00:07.672   222405 matches found
----------------
ultimate find(): 5.4.3.2.1. -> 0:00:06.531   222405 matches found
----------------
done

ultimate-find: func [
	series
	value

 index "field you want to search on, should be (1 <= index <= record-length)"
	record-length
	i "iterations"
	/local s st result
][
	prin "ultimate find(): "
	st: now/precise
	while [i > 0][
		prin i
		prin "."
		result: clear [] ;length? series
		s: at series index
		until [
			not all [
				s: find/skip s value record-length

    insert tail result copy/part skip s (-1 * index + 1) record-length
				s: skip s 3
			]
		]
		i: i - 1
	]
	
	prin join " -> " difference now/precise st
	print ["  " (length? result) / record-length "matches found"]
	
	head result
]

should have picked up that fourth index (1)

my advice would be:

1) to test Parse as Pekr noted (traversing only the respective field)
2) to use a hash to index the respective field

I think, that it is quite natural. You should probably generate some 
random data having (approximately) similar properties as what you 
intend to process and try some variant approaches to really find 
out, which one is best for the task. Do you know, that it is possible 
to index just a specific record field, i.e. you don't need to make 
a hash containing all the data from the database?

the only thing that I'm thinking is that when the hash index changes, 
its rehashing its content... which is strange.

terry, index? is not a procedure within rebol .. its the same as 
length?
its a stored value which is simply looked up when you call index?


nothing will be as fast as index?    its the "getting to" index which 
consumes cycles

but it will be 100 or 1000 times faster, then to access the data 
using an index.

The, I recovers its index from the block (actually it's the last 
one)

And i use this index as the value for the 3 indexes, and i create 
the keys+value
Tweety
: index
Isa
: index
Canary
: index

(added In index1) "Tweety"= index
(added In index2) "Isa"= index
(added In index3) "Canary"= index

(added In index1) "Tweety"= index
(added In index2) "Isa"= index
(added In index3) "Canary"= index

steeve, REBOL doesn't support path with strings, and furthermore, 
it would only return the first index, if you used it within a paren.


so I'd really like you to give a small snippet of code with your 
idea, I am curious about your method... cause I don't see *how* what 
you say works.

I would use map! (or hash!) as indexes and a key would contain one 
or several triples (inside a block)
verb/"age": [ index indexn ...]

To make it practical for other operations too, the triple store should 
be defined so, that:


1) every triple is stored as a fourtuple, the additional field being 
a unique triple ID
2) create the main index using the triple ID, 

3) create three field indices searchable by by the field contents, 
and "inside" also by the main ID


This way, the triple storage will be moderately fast for triple removal 
as well

Besides you don't need to store triples as blocks (they can be flattened) 
in the triple store, then you'll just need to do some math to calculate 
the index of a triple.

The advantage is that you could still use the triple store do some 
slow searchings.

To make it practical for other operations too, the triple store should 
be defined so, that:

1) every triple is stored as a fourtuple, the 
additional field being a unique triple ID...

Why not just use the index of the first part of the triple? 

ie: ["tweety" "isa" "canary" "Sylvester" "isa" "cat"...]


so 1 and 4 are the two triples( i1)  and the next two are i2 and 
i3

i1: [ "Tweety" [1] "Sylvester" [4][
i2: ["isa" [1 4]
i3: ["canary" [ 1] "cat" [4]]

so to determine what Sylvester is.. 

s: i1/("Sylvester")
>> [4]
p: i2/("isa")
>> [1 4]

do an intesect to get "4"
then the value = index ( 4) + 2

Why not just use the index of the first part of the triple?

 - yes, can be done that way, but if you need to remove the triples, 
 you find out, that it may be practical

how...

 - this way, you will have a triple ID that does not change even if 
 other triples are removed. That is not true for your index.

In my old AtomDB i made in Rebol some time ago, I had an index for 
each value.. ie: the number "42" was stored only once, and used the 
index with the inference.. 

values: [ "42" "November" "Baseball"..]


You could have a million birthdays recorded in "November", with a 
single element

billbdaymonth: 2
frankbdaymonth: 2
frankage: 1
the answer to life the universe and everything: 1

terry, any benchmark results on a dense search with a few million 
records?

also: how long is generating the index on that data

and how much RAM is your triple index consuming?

There's a fundamental flaw with this.. let say i find 3000 customers, 
but now i want to pull their email property

foreach customers  customer [ (pseudo) intersect the  customer with 
i1 and email i2)
once is fine.. but 3000 loops is really slow

probably need to store the properties as objects

data: [ "bob" [ email "[bob-:-example-:-com]" lname "Jones"] ...]

then continue to index email, lname etc

Steeve, back to your method with some changes.. 
Some early benchmarks on this new method
3,000,000 objects


subjects:  [ [age 42 fname "Steeve"][ fname "Tweety" age 75] [url 
"http://rebol.com"] ... ]

3,000,000 key / value pairs that index the subjects block

i1: [ "Steeve" 1 "Tweety" 2 "Rebol" 3 ... ] 

then.. 

	theindex: select i1 "Rebol"
	out: pick subjects theindex


I can do 1,000,000 of these in 1.3 seconds or one 769, 230 / s (older 
box with 2gb ram)

then finish the other two triples index (preds vals)

i2: [age [ 1 2] fname [1 2]  url [ 3]]

i3 should have it's values converted to md5s (as suggested) 

i3: [ #{12CE1E73A3EABF1623970A0C53B9CA1F} [3] ]

This doesn't look good ... http://www.curecode.org/rebol3/index.rsp


new issues are being created, but there's a sharp decline in closed 
issues

Ladislav and I have both written about our early experiences:
   http://www.rebol.org/art-display-index.r?a=R3

Note the use of the RCO object (REBOL Compatibility Object)  that 
attempts to make scripts R2 and R3 runnable.

I guess I'm saying that it would be a bug if it were only supposed 
to return the size of the file.  But  if it is to return the size 
of the remainder from the index position then I would say it is buggy. 
 Either way there is a problem with it. I just we keep so that it 
is returning from the index position.

>> extract/index [a b c d e] 2 2
== [b d none]

Is the last NONE desirable?

By example, the refinement /index has absolutly no interest.

The obvious and regular way with rebol, is to use SKIP or AT as a 
prefetch.

see.
extract/index [a b c d e] 2 2
vs.
extract at [a b c d e] 2

the second one is faster and even shorter to write :)

Henrik, the /index option of EXTRACT assumes that there will be something 
there at the index (record length specified is assumed), and that 
the R3-style treatment of series bounds is in effect. That means 
that the programmer is expected to do their own bounds checking, 
or to not care. The none value is a placeholder for missing data.

As for the reason for the inclusion of the EXTRACT function and its 
/index option, it is because of how much they are used, even in mezzanine 
code. There are a lot of functions there for our convenience, even 
if they would be easy to remake if missing. This doesn't make them 
less useful.

Actually, I used it on a table header with arbritrary data and simply 
wanted every second element in the block, regardless of the block 
content, so the block was not a db record of any known length. Perhaps 
it should be emphasized that extract/index works best on, or is intended 
for database records.

Correct is relative. EXTRACT/index is working as designed - it just 
wasn't doing what you wanted to do.

It's the mandatory width argument that makes EXTRACT record-oriented, 
not the /index option.

Max - this is imo wrong ... how is that usefull? I did not ask it 
return integer ... imo /index should still return original type

binary is a series, and indexes return, like all other series, the 
element which constitutes it at the index you give it.

Carl just posted this code, to be the new definition of EMPTY?:
empty?: make :tail? [
    [

        {Returns TRUE if empty or NONE, or for series if index is at or beyond 
        its tail.}
        series [series! gob! port! bitset! map! none!]
    ]
]

This means two things, one minor, one major:

- Minor: TAIL? won't take none, so we have an option of triggering 
the error if need be.

- Major: *You can do that kind of thing at all*. This opens a *lot* 
of possibilities :)

Graham:

If I want to set something to the index of a series, or something 
else if it's not there I have to do this

b: either a: find series var [
	index? a
][ 	default ]

when I'd rather do

 b: any [ index? find series var default ]

So how about letting index? also take none as an argument ?

Nope, 2.7.7 has the R2/Forward code. I see the bug, though have a 
question: Should the index obey the skip?

When /to is not specified and /skip is, offsets are multiplied by 
the record length, so you are counting in records. This is intentional, 
to allow you to work with fixed records without messing them up. 
If we keep that behavior then the index will be the record index, 
not the series index. It's not a difficult trick, but it should be 
noted.

The source is there already in case you need to use it before the 
next version comes out. The R3 version is:
move: func [
	"Move a value or span of values in a series."
	source [series!] "Source series"
	offset [integer!] "Offset to move by, or index to move to"
	/part "Move part of a series"
	length [integer!] "The length of the part to move"

 /skip "Treat the series as records of fixed size" ;; SKIP redefined
	size [integer!] "Size of each record"

 /to "Move to an index relative to the head of the series" ;; TO redefined
][
	unless length [length: 1]
	if skip [
		if 1 > size [cause-error 'script 'out-of-range size]
		offset: either to [offset - 1 * size + 1] [offset * size]
		length: length * size
	]
	part: take/part source length
	insert either to [at head source offset] [
		system/contexts/exports/skip source offset
	] part
]

In addition, I should note that all functions that require integral 
PAIR! fields now perform an internal round to "snap" them to nearest 
integers.  This applies not just to things like image size specs, 
but also to values like image pixel index pairs (something we support, 
but not often done, AFAIK)

2.100.99.3.1  the use of  function  at  with negative index simply 
returns the whole series - which reminds me to ask why   at   with 
index 0 doe not return the series atfter the last item i.e. place 
you at the end of the series?  The docs for  at   specify behavior 
for a negative index      "Using a negative index N, you can go N 
values backwards in a series:"   PS   I have relocated to Fredericton, 
NB, Canada.  Lovely, green and interesting.

Interesting. I think that's a bug, as CLEAR's spec is as follows:

clear: make action! [[

    {Removes all values. For series, removes from current index to tail 
    and returns tail.  (Modifies)}
    series [series! port! map! gob! bitset! none!]
]]

hum... maybe a way to build a context when building a function, with 
the index of each member of the body block mapped out to its original 
source.

exactly what I was pointing out earlier.    index, length suffix 
should have their ?  dropped.

Don't Mind. I have found the link: http://www.rebol.net/w/index.php?title=Copy_Semantics&redirect=no

It's a Core-only script, so the changes to create a version that 
runs under R3 (or even runs under R2 and R3) may be fairly simple.

Ladislav and I have both documented our early efforts to convert 
scripts. If someone does convert JSON.r, that may uncover other useful 
conversion guidelines.
   http://www.rebol.org/art-display-index.r?a=R3

http://www.rebol.net/w/index.php?title=Copy_Semantics&redirect=no

Was talking about the first form only (with the index)

To describe something else we would need to use something line INDEX-OF-MAXIMUM?, 
which is more accurate, but unnecessarily long to my taste

And it wouldn't be INDEX-OF-MAXIMUM?: First of all, the ? is inappropriate, 
secondly, it returns the series, not the index. FIND-MAX isn't less 
descriptive because it references the behavior of MAX (which we have 
already learned means maximum) and FIND (which we know returns the 
argument series at the position of the thing found). We don't only 
get our conceptual context from English, we also get it from the 
rest of REBOL.

http://www.rebol.net/w/index.php?title=Copy_Semantics&redirect=no

++ doesn't create a new series, it just increments the index of the 
reference to the same series.

SAME? must work from the same index in the same series:

== [a b c]
>> same? a next a
== false

Henrik, yes. I'm trying to point out, that an additional index is 
created.

And a block here is a series index. Two blocks can share the same 
mem area for the actual content of the series.

Maxim, a series reference only contains a pointer to the internal 
series structure and either a pointer to the offset or a 32bit index 
(Carl could say which). The internal series structure could have 
a pointer to the start of the series, or it could be a header of 
the series data itself, depending on which is better for memory allocation. 
What you see in extensions are marshalled values, not regular R3 
stack frames or other value slots.

yep. but we don't have the xtra information which links the data 
in the core, we only get the data.   in the extensions, we get a 
some sort of internal reference to the series and the index.   this 
is how I see it working in the core too.   there is ample room for 
this info in 128 bits.

A series value does not include an index. Only a reference does. 
So that's one indirection, from a value slot (with an index) to a 
series value

Desiding what to do with block indexes out of range is a tough call, 
I think. I understand the argument not to cause errors, if it can 
be handled somehow, but I'm not sure, handling out-of-range problems 
is always good. What if it's a user bug in the code, that made the 
index get out of range? Then the user won't easily find that bug, 
as it causes no error.


It's not possible to index a block lower than 1 (first element). 
It's only possible to index out of range in the other end of the 
block, getting past the tail. And that can only be done by having 
an index there, and then remove something from earlier in the block. 
When the index is beyond the tail, then it has to be desided what 
to do with
	insert, remove, skip, next, back, pick, select, append
used on that index. (and maybe more like TAIL?, INDEX?, ...)

What does other languages do?

Let's say, my index is way beyond the tail, and I insert a new element 
there. It may then just be appended to the series, which is at an 
index way before my pointer. What if I then e.g. say:
	remove/part my-index -1

Let's say, my index is way beyond the tail, and I insert a new element 
there.
 - you are out of luck, such an operation is not supported

BTW, "Let's say, my index is way beyond the tail, and I insert a 
new element there." - in fact, I was right saying that the operations 
was not supported, since it did not insert a new element there

I think that the incompatibility of NEXT and BACK is more important, 
and definitely an error, and an accident.
>> a: [1 2 3]
== [1 2 3]
>> b: skip a 2
== [3]
>> remove/part a 3
== []
>> index? b
== 3
>> index? next b

== 3  ; constrained to the argument index, not even the series bounds
>> index? back b
== 2 ; not constrained to the series bounds
>> index? back a
== 1 ; constrained to the head

Right.

For blocks, inserting doens't change position of other indexes to 
same series. What I expect, is that the insert is from the index 
given, before the insert is carried out. Like:

>> s: [a b c]
>> insert/only s skip s 2
should result in
	[[c] a b c]

, where the first element is a pointer to one before the end of s, 
not two before the end of s as we have today.

The above list example proves, that lists don't "know" their index, 
and have to calculate it every time, which means, that "index access" 
is slow.

As opposed to that, blocks are designed for fast index access, so 
they have to "know" it, which means, that INSERT cannot change it

I don't think, INSERT have to change position of some index, it just 
have to insert the next position than the one given, and only if 
insert is earlier in the same series.

I don't think, INSERT have to change position of some index
- that formulation does not make sense to me

index is a number

I read you, as INSERT cannot change an index. I say, INSERT should 
just add 1 to the index number, it receives, and only in that special 
case.

just realize, that index is a number, and every blocks remembers 
it

and, since the index attribute is immutable, in fact, the INDEX function 
cannot change it

I'm not talking about calculating every time and changing of indexes 
being hold by variables and such. I only suggest, that INSERT does 
this:


If /only and if value being inserted is an index (or position or 
what we should call it) later in the same series, where we are inserting, 
add 1 to the index value and insert that.
In all other cases carrie on as usual.

Alright 2010 is almost over now. Why don't we set something up virtually 
and "just do it"?  I just had a Teamviewer http://www.teamviewer.com/download/index.aspx?os=windows
session with some people from Singapore and Taiwan from California 
and it worked flawlessly. You guys sound like you are all doing some 
very interesting things.

with a functional /library interface stuff like this will be
possible in rebol, quite interesting. 
If you like visualisation take a look here:

http://www.panopticon.com/demo_gallery/d_bats_usa_ex_demo.htm

for an overview:

http://www.panopticon.com/demo_gallery/index.php

Try read (write etc) like this:

     read [ scheme: 'ftp host: domain.com user: user-domain.com pass: 
     "password" ]

Or see what other people have tried in the past:
    http://www.rebol.org/ml-topic-index.r?i=ftp

yes looks pretty decent... a nice wrap up here:
http://corte.si/posts/code/timsort/index.html