<bgk>
If i had a list and i wanted to perform a repeated an operation on the list without the i'th (i=1..List.length) element, what would be the best way to do it?
<bgk>
E.g. let v = [1;2;3;4;5] I want to compute f([2;3;4;5]), f([1;3;4;5]) f([1;2;3;5]) and f([1;2;3;4])
<bgk>
(and f([1;2;4;5]) )
<bgk>
i have a solution but it's very slow on a list with only 10k elements.
<bgk>
(yes, the complexity is List.length^2, but still, it shouldn't take > 20mins to run, surely?)
Cyanure has quit [Remote host closed the connection]
lopex has joined #ocaml
<thelema>
bgk: well, creating the n lists each without the ith element could be done progressively
<thelema>
Is the f function a fold? i.e. do you need the two halves of the list joined?
<bgk>
f is a non-linear function applied to each element of the list in turn
<thelema>
is it associative?
<thelema>
or rather, can f be computed as g (f(head of list), f(tail of list)) or somesuch?
<thelema>
It'd be extra nice if f were commutative, so that the order of the list didn't matter, but that's probably too much to hope
<bgk>
let me think
<thelema>
in any case, if you can partially apply f to elements of the list one at a time you can get partial results for slices [1], [1;2], [1;2;3], etc.
<thelema>
getting the tail slices is also straightforward, as you just pop off the head of the list.
<thelema>
"finishing" f([1]) with the tail [3;4;5] gets you the first result
<thelema>
then f[1;2] gets finished with [4;5]
<thelema>
etc.
<bgk>
unfortunately f operates on the whole drop-one lists
<bgk>
and actually takes the element that was dropped as an argument too
<thelema>
you can easily have the dropped element as an argument.
lopex has quit []
<thelema>
If you need to apply a procedure to each element of the sublists in turn,
lopex has joined #ocaml
<thelema>
let rec loop pre = function [] -> assert false | [x] -> f pre [] x | elem::post -> f pre post elem; loop (pre @ [elem]) post
<thelema>
If you can have pre in reverse order, you can do (elem :: pre), and gain a ton of efficiency...
<bgk>
i am trying to parse what you jsut wrote there :-)
<bgk>
what is this clause doing ? "f pre post elem; loop (pre @ [elem]) post"
<thelema>
running f on the head, tail and element dropped
<thelema>
and then recursively calling the loop with a new pre and post
<thelema>
this all assumes f is a unit function, if you want to accumulate some result from f (maybe a list of results), add an accumulator and push f's return value onto it.
Ruempelstilzchen has quit [Read error: Operation timed out]
<thelema>
make sense?
<bgk>
hmm still playing with it!
<bgk>
this is my first day of ocaml.
<bgk>
i did some Haskell years ago
Ruempelstilzchen has joined #ocaml
<bgk>
it's not doing what i expect. i defined f = List.map (fun z -> z*x) (List.concat [pre;post]);;
<bgk>
for example... and apply to [2;3;4] .. im expecting to see 2*[3;4], 3*[2;4], 4*[2;3] say ?
<thelema>
well, it's currently ignoring the result of f, just running f without using the result
<thelema>
List.concat [pre;post] isn't a good way to do it. Better is (pre@post), best is something more complex
<bgk>
i just saw that from your code :)
<bgk>
so if wanted to say sum up these values
enthymeme has quit [Quit: rcirc on GNU Emacs 23.1.1]
<bgk>
i mean the result of these strange operation i am doing
<bgk>
i might do
<bgk>
let rec loop pre = function [] -> assert false | [x] -> f pre [] x | elem::post -> f pre post elem @ loop (pre @ [elem]) post;;
<bgk>
and then sum t he list ?
<bgk>
yeah .. ok that seems to work
<bgk>
thanks thelema!
fremo__ has quit [Read error: Connection reset by peer]
fremo__ has joined #ocaml
<thelema>
I don't think you want that...
<thelema>
better is:
<thelema>
let rec loop acc pre = function [] -> assert false | [x] -> (f pre [] x) :: acc | elem::post -> loop ((f pre post elem)::acc) (pre @ [elem]) post
<thelema>
don't over-use @, it costs O(len(first list))
<thelema>
if you can use batteries from git, the batDeque module has constant time concatenation, which would solve the @ problem
<thelema>
hmm, not constant time, O(min(m,n))... odd, I thought deques could be catenated in constant time
tauntaun has joined #ocaml
<bgk>
and after that.. doesn't seemmuch quicker than what i had!
<bgk>
thank you though thelema. I learned a few things. I'll keep playing
<bgk>
(i'll try the batDeque thing too)
<thelema>
well, you are computing f 10K times on 10K elements - that's 100M elements for f to process.
<thelema>
the Deque thing will cut down the costs of the list processing, but won't help the total cost of f. Maybe if you can reuse any computations... Or maybe you're just trying to do something expensive.
<bgk>
it's somewhat expensive, it's a cross-validation bandwidth selection for kernel density estimation :-)
<bgk>
thanks again! off to bed.
<bgk>
more OCaml tomorrow!
bgk has left #ocaml []
enthymeme has joined #ocaml
npouillard has quit [Ping timeout: 248 seconds]
<EM03>
I think i will use python in the near future here for my web dev but i would like to use ocaml but there is such a lack of frameworks
lopex has quit []
npouillard has joined #ocaml
tauntaun has quit [Quit: Ex-Chat]
philtor has joined #ocaml
<orbitz>
EM03: i've been moving away from Python for most stuff. Have you cehceked out Ocsigen?
dnolen has quit [Quit: dnolen]
enthymeme has quit [Quit: rcirc on GNU Emacs 23.1.1]
sepp2k has quit [Quit: Leaving.]
schmrkc has quit [Ping timeout: 250 seconds]
schmrkc has joined #ocaml
schmrkc has quit [Changing host]
schmrkc has joined #ocaml
thelema_ has joined #ocaml
thelema has quit [Remote host closed the connection]
Pepe_ has quit [Ping timeout: 250 seconds]
jonafan__ has joined #ocaml
Pepe_ has joined #ocaml
jonafan_ has quit [Ping timeout: 252 seconds]
philtor has quit [*.net *.split]
lamawithonel has quit [*.net *.split]
shachaf has quit [*.net *.split]
alpounet has quit [*.net *.split]
vk0 has quit [*.net *.split]
bzzbzz has quit [*.net *.split]
Julien_t has quit [*.net *.split]
pheredhel has quit [*.net *.split]
iris1 has quit [*.net *.split]
trigen has quit [*.net *.split]
pantsd_ has quit [*.net *.split]
philtor has joined #ocaml
lamawithonel has joined #ocaml
shachaf has joined #ocaml
alpounet has joined #ocaml
vk0 has joined #ocaml
bzzbzz has joined #ocaml
Julien_t has joined #ocaml
pheredhel has joined #ocaml
iris1 has joined #ocaml
trigen has joined #ocaml
pantsd_ has joined #ocaml
surikator has quit [Quit: Scientific discovery is just maximal compression of random strings. Nothing more, nothing less.]
Ruempelstilzchen has quit [Ping timeout: 252 seconds]
Snark_ has joined #ocaml
ikaros has joined #ocaml
Snark_ is now known as Snark
ikaros has quit [Quit: Leave the magic to Houdini]
Yoric has joined #ocaml
Yoric has quit [Read error: Connection reset by peer]
Yoric has joined #ocaml
Yoric has quit [Read error: Connection reset by peer]
Yoric has joined #ocaml
ikaros has joined #ocaml
ski__ is now known as ski
ygrek has joined #ocaml
philtor has quit [Ping timeout: 255 seconds]
edwin has joined #ocaml
Yoric has quit [Quit: Yoric]
ymasory has quit [Ping timeout: 248 seconds]
EM03_ has joined #ocaml
EM03_ has quit [Changing host]
EM03_ has joined #ocaml
EM03 has quit [Read error: Connection reset by peer]
EM03_ is now known as EM03
lamawithonel has quit [Ping timeout: 255 seconds]
lamawithonel has joined #ocaml
EM03 has quit [Quit: EM03]
bzzbzz has quit [Ping timeout: 255 seconds]
ygrek has quit [Ping timeout: 246 seconds]
bzzbzz has joined #ocaml
lamawithonel has quit [Ping timeout: 240 seconds]
lamawithonel has joined #ocaml
ygrek has joined #ocaml
EM03 has joined #ocaml
Yoric has joined #ocaml
lamawithonel has quit [Ping timeout: 240 seconds]
lamawithonel has joined #ocaml
<eye-scuzzy>
say test
vouillon has quit [Remote host closed the connection]
edwin has quit [Quit: Leaving.]
edwin has joined #ocaml
vivanov has joined #ocaml
lopex has joined #ocaml
lopex has quit []
ankit9 has joined #ocaml
strlen has quit [Ping timeout: 246 seconds]
strlen has joined #ocaml
_y_ has joined #ocaml
_andre has joined #ocaml
vivanov has quit [Ping timeout: 246 seconds]
vivanov has joined #ocaml
_y_ has quit []
ftrvxmtrx has quit [Read error: Operation timed out]
ftrvxmtrx has joined #ocaml
vivanov has quit [Ping timeout: 248 seconds]
vivanov has joined #ocaml
ygrek has quit [Ping timeout: 246 seconds]
ttamttam has joined #ocaml
ttamttam has quit [Remote host closed the connection]
Oejet has joined #ocaml
Yoric has quit [Read error: Connection reset by peer]
Yoric has joined #ocaml
tauntaun has joined #ocaml
dnolen has joined #ocaml
dnolen has quit [Excess Flood]
dnolen has joined #ocaml
dnolen has left #ocaml []
tauntaun has quit [Ping timeout: 255 seconds]
sepp2k has joined #ocaml
vivanov has quit [Quit: leaving]
ygrek has joined #ocaml
Oejet1 has joined #ocaml
Oejet has quit [Ping timeout: 276 seconds]
ygrek has quit [Ping timeout: 246 seconds]
avsm has quit [Ping timeout: 250 seconds]
tauntaun has joined #ocaml
ttamttam has joined #ocaml
avsm has joined #ocaml
hcarty has quit [Ping timeout: 260 seconds]
ttamttam has left #ocaml []
Oejet1 has quit [Read error: Connection reset by peer]
Oejet has joined #ocaml
boscop_ has joined #ocaml
boscop has quit [Ping timeout: 248 seconds]
avsm has quit [Quit: Leaving.]
avsm has joined #ocaml
jonafan__ has quit [Quit: Leaving]
jonafan has joined #ocaml
joewilliams_away is now known as joewilliams
avsm has quit [Quit: Leaving.]
boscop_ is now known as boscop
npouillard has quit [Ping timeout: 248 seconds]
hcarty has joined #ocaml
npouillard has joined #ocaml
avsm has joined #ocaml
mcclurmc has quit [Quit: Leaving.]
mcclurmc has joined #ocaml
vivanov has joined #ocaml
Ruempelstilzchen has joined #ocaml
Oejet has quit [Ping timeout: 276 seconds]
tauntaun has quit [Quit: Ex-Chat]
Yoric has quit [Quit: Yoric]
vk0 has quit [Ping timeout: 255 seconds]
ymasory has joined #ocaml
Oejet has joined #ocaml
edwin has quit [Ping timeout: 252 seconds]
edwin has joined #ocaml
Oejet has quit [Quit: Leaving.]
rwmjones has quit [Read error: Operation timed out]
fraggle_ has quit [Ping timeout: 240 seconds]
fraggle_ has joined #ocaml
rwmjones has joined #ocaml
avsm has quit [Quit: Leaving.]
tauntaun has joined #ocaml
Yoric has joined #ocaml
rwmjones has quit [Read error: Operation timed out]
rwmjones has joined #ocaml
npouillard has quit [Ping timeout: 264 seconds]
npouillard has joined #ocaml
ftrvxmtrx has quit [Ping timeout: 264 seconds]
ftrvxmtrx has joined #ocaml
hcarty has quit [Quit: leaving]
hcarty has joined #ocaml
Snark has quit [Quit: Ex-Chat]
mehdid has quit [Ping timeout: 260 seconds]
_andre has quit [Quit: leaving]
mehdid has joined #ocaml
lopex has joined #ocaml
vk0 has joined #ocaml
boscop has quit [Ping timeout: 255 seconds]
boscop has joined #ocaml
vk0 has quit [Read error: Operation timed out]
Yoric has quit [Quit: Yoric]
ymasory has quit [Ping timeout: 255 seconds]
vk0 has joined #ocaml
Yoric has joined #ocaml
vivanov has quit [Ping timeout: 260 seconds]
vivanov has joined #ocaml
Ruempelstilzchen has quit [Ping timeout: 240 seconds]
vk0 has quit [Read error: Operation timed out]
avsm has joined #ocaml
vk0 has joined #ocaml
enthymeme has joined #ocaml
ikaros has quit [Quit: Leave the magic to Houdini]
Yoric has quit [Quit: Yoric]
tauntaun has quit [Quit: Ex-Chat]
edwin has quit [Remote host closed the connection]
tauntaun has joined #ocaml
tauntaun has quit [Read error: Connection reset by peer]
Associat0r has joined #ocaml
myu2 has quit [Remote host closed the connection]
Amorphous has quit [Read error: Operation timed out]
dnolen has joined #ocaml
Amorphous has joined #ocaml
tauntaun has joined #ocaml
Obfuscate has quit [Read error: Operation timed out]