Vincenz has quit [Read error: 104 (Connection reset by peer)]
docelic is now known as docelic|sleepo
jao has quit ["leaving"]
Kinners has joined #ocaml
<teratorn>
say i've got a big string, and a smaller string, and i want to test if the smaller string exists within the bigger one beginning at a certain offset?
<teratorn>
this needs to be fairly efficient since this comparrison is going to happen *allot*
lus|wazze has quit ["Syntactic sugar causes cancer of the semicolon"]
<Kinners>
and the Str module of course, I don't know if it's made for all out speed though
<teratorn>
thanks ill check it out
<Kinners>
the biocaml.org project also has some string stuff which could be quite fast
<teratorn>
maybey ill just write my own function, should be pretty easy
vincenz has joined #ocaml
pattern_ has quit [Read error: 110 (Connection timed out)]
<teratorn>
anyone know the differences in the real memory storage structure between list's and arrays?
<teratorn>
is there a way to aceess list elements by index number?
<Kinners>
yes, using the List module
<Kinners>
but it's still just iterating through them
<teratorn>
so List.nth
<teratorn>
i'm curious which structure provides faster index access
<teratorn>
i just need to stuff a few handfuls of constant data into some kind of sequence
<teratorn>
i wonder why list's don't have syntax for index access
<Kinners>
arrays are made of boxed or unboxed contiguous elements
<Smerdyakov>
Because getting a list item takes time proportional to its index.
<teratorn>
by boxed you mean referenced?
<teratorn>
Smerdyakov: oh that sucks
<Kinners>
they're not designed for indexed access
<teratorn>
but an array, in memory, it's just a contiguous sequence of pointers?
<Kinners>
yes, and in some cases unboxed
<teratorn>
i see
<teratorn>
unboxed for immutable values?
<Kinners>
I can't remember which ones are unboxed, but possibly int, float and char
<teratorn>
would it really have to be fixed-length values only?
<Kinners>
I don't know the exact details
rhil is now known as rhil_zzz
reltuk has joined #ocaml
<reltuk>
can I make a disjoint type with 'a's?
<reltuk>
I wanted to do like --> type search_result = Result 'a * 'a * bool | EmptyResult
<Riastradh>
'Result of 'a * 'a * bool', not 'Result 'a * 'a * bool'.
<reltuk>
"Unbound type parameter 'a"
<Riastradh>
Oh, yeah.
<reltuk>
the missing "of" was an irc typo :-p
<Riastradh>
'type 'a search_result', too.
<reltuk>
ahhh, awesome
* reltuk
loves the ocaml type system
SteveO has joined #ocaml
SteveO has left #ocaml []
Smerdyakov has quit ["sleep"]
Kinners has left #ocaml []
GreyLensmen has quit ["Client Exiting"]
<reltuk>
how do you include another source file in a source file?
<teratorn>
make it a module
<reltuk>
umm..I just have a ml file
<teratorn>
so?
<reltuk>
and some other caml object files that I have to link against
<reltuk>
they used this .ml file, so I need to...
<teratorn>
you have some code, you want to put it into another file, and you want to use it from the original file?
<reltuk>
yeah
<teratorn>
so you make it a module, then you can use it like any other module
<reltuk>
good stuff, thx
cDlm_ has joined #ocaml
cDlm has quit [Read error: 60 (Operation timed out)]
whee has quit ["Leaving"]
pattern_ has joined #ocaml
mattam_ has quit ["brb"]
mattam has joined #ocaml
cDlm_ is now known as cDlm
docelic|sleepo is now known as docelic
cDlm has quit [Read error: 104 (Connection reset by peer)]
cDlm has joined #ocaml
cDlm has quit [Killed (NickServ (Ghost: cDlm!cdlm@lns-th2-12-82-64-183-88.adsl.proxad.net))]
cDlm has joined #ocaml
teratorn has quit [Remote closed the connection]
teratorn has joined #ocaml
* teratorn
ponders
<teratorn>
I have a bunch of characters, and i need to see if another char matches one of them and know which one it is
<teratorn>
how could i sort the sequence of chars and then do a binary search on it?
<teratorn>
it would be really great if someone had some simple example code for the Map module
reltuk_ has joined #ocaml
reltuk has quit [Remote closed the connection]
<teratorn>
or maybey i don't want a binary search. what's the name of that search algo where it starts in the middle of an ordered sequence, and keeps cutting the area left to search in half?
<teratorn>
oh nm, that's what it is
TachYon has joined #ocaml
cDlm_ has joined #ocaml
cDlm has quit [Killed (NickServ (Ghost: cDlm_!cdlm@lns-th2-10-82-64-154-94.adsl.proxad.net))]
reltuk has quit [Read error: 54 (Connection reset by peer)]
<mrvn_>
Anyone started on the ICFP?
<mellum>
mrvn_: wanna start? You only missed 12 hours yet :)
<mrvn_>
Looks like a good job for a genetic algorithm.
<mellum>
Yeah.
<cDlm>
fuzzy logics would give nice solutions, but possibly not optimal
<mellum>
Too bad I'm so lazy today.
<mrvn_>
Hmm, some tracks look realy mean.
TachYon has quit [Remote closed the connection]
<mellum>
I'd just define a few waypoints by hand.
lus|wazze has joined #ocaml
pattern_ has quit [Read error: 60 (Operation timed out)]
pattern_ has joined #ocaml
pattern_ has quit [Read error: 110 (Connection timed out)]
pattern_ has joined #ocaml
Smerdyakov has joined #ocaml
pattern__ has joined #ocaml
pattern_ has quit [Read error: 104 (Connection reset by peer)]
plonkaz has quit ["[BX] Pretzel Boy uses BitchX. Shouldn't you?"]
rox has quit ["Client exiting"]
GnuVince has joined #ocaml
mrvn has joined #ocaml
<teratorn>
so how do i perform a binary search on a sorted array?
<mrvn>
you look at the middle of an interval and then decide if what you search is left or right of that.
<teratorn>
right i know how it works
<teratorn>
is there a built-in function for it?
<mrvn>
Why should there.
<teratorn>
eh?
<mrvn>
Use a set or hashtbl.
<teratorn>
so i don't have to write it, of course. :)
<teratorn>
well
<mrvn>
With a sorted array you should implement dictionary search instead.
<teratorn>
hm how does that work?
mrvn_ has quit [Read error: 110 (Connection timed out)]
Zadeh has quit [Read error: 104 (Connection reset by peer)]
<teratorn>
man i'm googling and i can't find anything about dictionary searches :(
<mrvn>
How do you look up something in a dictionary?
<mrvn>
Do you read it from start to end? No. Do you open it in the middle and see if its before or after that? Not exactly.
<mrvn>
You guess where the right word roughly is and look there. Then you see how far your off and guess again in the remaining part.
<vegai>
you ask someone else do it
<mrvn>
For example for a word starting with B you would open the dictionary ~1/26 from the start.
<mrvn>
If you have an even distribution of keys dictionary search is O(log log n)
<mrvn>
Anyone doing the icfp?
* Riastradh
is.
<mrvn>
In ocaml?
<Riastradh>
No, in Scheme.
<mrvn>
that sucks.
<vegai>
how come?
<mrvn>
no types
<mrvn>
I was hoping to borrow someone elses simulation.
<vegai>
umm...
<mrvn>
The 25 bit fixpoint arithmetics suck.
<mellum>
mrvn: why? doesn't seem to be that hard... just make an abstract data type of it
<mrvn>
mellum: on i386 an int is to small.
<mellum>
who cares? use int64.t
<mrvn>
Thats boxed and slow.
<mrvn>
does Int64.div round towards zero?
<mellum>
I don't think that will produce such a terrible slowdown
<mellum>
I mean, if other people are using Scheme... ;)
<lus|wazze>
itd probably be faster to do it by hand with pairs of ints instead of with the boxed Int64.t type
<lus|wazze>
type fix25 = { whole_part : int ; fractional_part : int }
<mrvn>
Then you need to reimplement all the arithmetics.
<lus|wazze>
of course
<lus|wazze>
but you have to do that anyway
<lus|wazze>
except if there already IS a fixed-point arithmetic type in ocaml that im not aware of ...
<mellum>
Just write a C extension and store it in an abstract data type. Then you can do it in assembly :)
<mrvn>
better storing it as int.
<mellum>
but actually, shouldn't it suffice to use an int as representation? You should need more precision only for *intermediary* results
<mrvn>
and converting it to long long fior * and / in C.
<lus|wazze>
well if your gonna do it in assembly, iirc the fpu can do fixed-point arithmetic already
<lus|wazze>
at least with MMX
<mellum>
But really, a factor of 2 or 10 here won't really matter compared to general algorithmic cleverness, I'm sure
<lus|wazze>
well i have to say i dont think this year's contest's task is very interesting
<lus|wazze>
the best so far was the raytracer one (where iirc ocaml won as well)
<mellum>
I like it, too.
lus|wazze has quit ["Syntactic sugar causes cancer of the semicolon"]
lus|wazze has joined #ocaml
rox has joined #ocaml
<mrvn>
Ok, fixpoint and car is done. Now I need to represent the track.
<mellum>
Well, an enum array array suggests itself naturally
<mrvn>
And no nice colors?
<mellum>
We don't need no stinkin' colors!
<teratorn>
lus|wazze: i though last years robot contest was awsome
<teratorn>
lus|wazze: but other than that, all pretty boring
<mrvn>
How do I wait some seconds without Unix.sleep?
<mrvn>
never mind, I just didn't wait enough.
<mrvn>
let rec wait = function 0 -> () | x -> wait (x-1)
<mrvn>
let _ = wait 1000000000
<mrvn>
cpus nowadays are too fast
<vegai>
if you do that, the process will take near 100% CPU
<mrvn>
yeah, who cares. I just want to see the result before it quits.
<vegai>
okie =)
<mellum>
mrvn: maybe it gets optimized away :)
<mrvn>
Thats what I thought but no. I was just not waiting long enough.
<mrvn>
Hmm, where is up in those tracks?
<mellum>
mrvn: well, one of them contains some letters, so you can tell :)
<mrvn>
(0,0) is the top left edge
<teratorn>
mrvn: i couldn't find anything about dictionary array searching do you have a url or anything? should i just use a binary search?
<mrvn>
But sin/cos are done in the math way.
<mrvn>
agh no, angles are clockwise so it works.
<mellum>
mrvn: well, they state the algorithms for sin/cos pretty explicitely, you just have to copy them :)
<mrvn>
I now have a framewrok that reads and displays the track via Graphics module and the simulation hopefully works too.
<mrvn>
Time to start solving.
<mellum>
mrvn: genetic algorithm?
<mrvn>
no, I think A* first
<mrvn>
Or in a way a genetic algorithm. Each iteration each car splits into all possible actions to be taken and only the fastest million cars are allowed to live.
<mrvn>
A car takes way too much ram. With ~5000000 cars I run out of ram.
<mellum>
Buy more memory.
<mrvn>
The timesteps are way to small.
<mrvn>
I guess a solutions needs about 100000-1000000 steps.
<mellum>
really? and then it has to be transferred via modem? Sounds like fun :)
<mellum>
also, makes a draw extremely unlikely :)
<mrvn>
Should compress very well.
<mrvn>
With 1000 steps just accelerating I get ~150 pixel far.
<mrvn>
Problem is how to weed out slower cars.
<mrvn>
How do I calculate how far a car is from the goal?