[Caml-list] [OCAML]:: the cost of List.length

[Caml-list] [OCAML]:: the cost of List.length

[沈胜宇]

[-- Attachment #1: Type: text/plain, Size: 255 bytes --]

Dear all:


I have a program that run very fast.


Recently, I add a call to List.length to this old program's inner loop, which make it significantly slower.


So what is the cost of List.length, is it liner to the size of the list? or is a const?


Shen

[-- Attachment #2: Type: text/html, Size: 347 bytes --]

Re: [Caml-list] [OCAML]:: the cost of List.length

[Malcolm Matalka]

[-- Attachment #1: Type: text/plain, Size: 355 bytes --]

O(n)
Den 14 apr 2013 15:27 skrev "沈胜宇" <syshen@nudt.edu.cn>:

> Dear all:
>
> I have a program that run very fast.
>
> Recently, I add a call to List.length to this old program's inner loop,
> which make it significantly slower.
>
> So what is the cost of List.length, is it liner to the size of the list?
> or is a const?
>
> Shen
>

[-- Attachment #2: Type: text/html, Size: 666 bytes --]

Re: [Caml-list] [OCAML]:: the cost of List.length

[David House]

Lists are naive linked lists, i.e. either the empty list or a pair of
an element and a list. Finding the length means walking to the end of
the list.

There is probably a better data structure than lists for your
purposes. What operations do you need, and which ones need to be fast?

On 14 April 2013 14:32, Malcolm Matalka <mmatalka@gmail.com> wrote:
> O(n)
>
> Den 14 apr 2013 15:27 skrev "沈胜宇" <syshen@nudt.edu.cn>:
>
>> Dear all:
>>
>> I have a program that run very fast.
>>
>> Recently, I add a call to List.length to this old program's inner loop,
>> which make it significantly slower.
>>
>> So what is the cost of List.length, is it liner to the size of the list?
>> or is a const?
>>
>> Shen

Re: Re: [Caml-list] [OCAML]:: the cost of List.length

[沈胜宇]

Dear all:

I have found that the slow down of my program is not caused by the List.length directly, instead, the list length operation cause some different change in my control flow, that is the direct cause of my slow down.

but still thank you for your help.

Shen


> -----原始邮件-----
> 发件人: "David House" <dhouse@janestreet.com>
> 发送时间: 2013-04-15 14:29:21 (星期一)
> 收件人: "Malcolm Matalka" <mmatalka@gmail.com>
> 抄送: "沈胜宇" <syshen@nudt.edu.cn>, caml-list <caml-list@inria.fr>
> 主题: Re: [Caml-list] [OCAML]:: the cost of List.length
> 
> Lists are naive linked lists, i.e. either the empty list or a pair of
> an element and a list. Finding the length means walking to the end of
> the list.
> 
> There is probably a better data structure than lists for your
> purposes. What operations do you need, and which ones need to be fast?
> 
> On 14 April 2013 14:32, Malcolm Matalka <mmatalka@gmail.com> wrote:
> > O(n)
> >
> > Den 14 apr 2013 15:27 skrev "沈胜宇" <syshen@nudt.edu.cn>:
> >
> >> Dear all:
> >>
> >> I have a program that run very fast.
> >>
> >> Recently, I add a call to List.length to this old program's inner loop,
> >> which make it significantly slower.
> >>
> >> So what is the cost of List.length, is it liner to the size of the list?
> >> or is a const?
> >>
> >> Shen