About alternatives to Matlab

[Jon Harrop]

Filip Wasilewski wrote:
> Jon Harrop wrote:
>> Filip Wasilewski wrote:
>> > Jon, both Python and Matlab implementations discussed here use the
>> > lifting scheme, while yours is a classic convolution based approach.
>>
>> I've done both in OCaml. The results are basically the same.
> 
> Have you tried taking advantage of the 50% reduction of arithmetic
> operations for the lifting scheme?

Yes. The time taken is dominated by memory accesses. The amount of
arithmetic is almost irrelevant.

>> It makes sense because they solve the same problem. When you're comparing
>> non-trivial problems between disparate languages you are not likely to
>> use the same algorithms. Using built-in hash functions is an obvious
>> example.
> 
> I don't even ask if you have checked the output result coefficients
> because I'm pretty sure you have not.

I checked the coefficients against other DWTs from the web.

> They solve similar problem but in 
> different ways and give a bit different results, for example the
> layout of coefficients in the memory is different as well as border
> distortion handling. Please don't tell me it's better to do something
> else instead of presenting a relevant solution.

I used a more efficient approach because I could. Using a compiled language
gave me that choice. We should compare both approaches in both languages.

>> No. The effects you are talking about are swamped by the interpreted vs
>> compiled effect.
> 
> Have I already mentioned it was observed with low-level C
> implementation on x86? I would really appreciate you took some time on
> exploring the unfortunate topic of this benchmark before posting
> another comment like that.

We are talking about this Python implementation, not some "low-level C
implementation on x86". With Python, it is the overhead of the interpreter
that makes it slow and encourages you to obfuscate your code in order to
make it run in a reasonable amount of time.

> What I would really like to see is a lifting scheme 
> implementation that can take 1- to 10-dimensional arrays

I believe that is just a case of abstracting get/set.

> (single and double precision floats,

That is also a case of abstracting get/set.

> convert on the fly from integer types when necessary

That is dynamic typing.

> and handle strided, non-contiguous arrays),

That is also an abstraction of get/set.

> axis and maximum decomposition level as input

I don't know what that is.

> and return list of views (or arrays if necessary)

Probably just a closure.

> with transform coefficients for every level of 
> decomposition. Can do?

Sure. Sounds like a lot of work though. This would be best done in F#
because you can make your own IList derivatives with get_Item and set_Item
that provide views but look like arrays.

> Are you telling I have to define a different operator for every
> arithmetic operation for every two types?

In OCaml, yes. Not in F#.

> That definitely does not look 
> like a quick, flexible and clear solution to start with. Any working
> example I could type into OCamlWinPlus of the following would be very
> appreciated. I'm fairly new to this and would really like to see how to
> handle differently shaped arrays and data types in the interactive mode
> without much hassle:
> 
> from numpy import ones, arange, reshape, int32
> a = ones((2,3,4,5))
> b = ones(a.shape, dtype=int32)
> c = ones((3,4,5))
> d = 2*a + 2.5*(3*b + 3.3)
> d[0] = d[0] + 5
> d[1] *= c * (2+3*1.2)
> d[:,2,...] = reshape(arange(d[:,2,...].size), d[:,2,...].shape)
> print d[...,1]

I can't get that to work in Python. What do I need to do?

>>> import numpy
>>> a = ones((2,3,4,5))
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
NameError: name 'ones' is not defined

> The ray tracer example is really nice, however the sudoku solver is not
> so impressive when compared to the K thingy ;-) -
> http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver.

Well, OCaml does ok on the sudoku but K does awfully on the ray tracer.

>> > I was also unable to run your OCaml example for n >= 2^21 (win32, out
>> > of the box OCaml installation). Is there some 16MB memory limit imposed
>> > on Array?
>> > # let q = Array.make (1 lsl 21) 0.0;;
>> > Exception: Invalid_argument "Array.make".
>>
>> On 32-bit, yes. You'd either have to use a different data structure
>> (Bigarrays), upgrade or switch to F#.
> 
> That renders the Array type almost useless for me. Where can I find
> documentation or tutorial on using Bigarrays?

http://caml.inria.fr/pub/docs/manual-ocaml/libref/Bigarray.html

You probably want to use F# though.

-- 
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/index.html?usenet