| Author |
Message |
|
| nm at web.am |
 Posted: Wed May 25, 2005 6:15 pm |
 |
|
|
Guest
|
Hi all!
are there any really fast ways to remove last element from list?
list size is 5-15 elements, but it's not known at compile time.
I need to implement something like FIFO, new elements inserted in list
push old elements out.
now it looks line
NewList = [ Elem | lists:sublist(List, N-1)]
which probably is not the best way.
--
Gaspar Chilingarov
System Administrator
t +37491 419763
w www.web.am
e nm@web.am
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| vladdu |
| Posted: Wed May 25, 2005 6:41 pm |
|
|
|
User
Joined: 28 Feb 2005
Posts: 397
Location: Gothenburg, Sweden
|
----- Original Message -----
From: "Gaspar Chilingarov" <nm@web.am>
> I need to implement something like FIFO, new elements inserted in list
> push old elements out.
Try the queue module, it does what you want and it's interesting to look at
the implementation.
/Vlad
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
 
|
| svg at surnet.ru |
| Posted: Wed May 25, 2005 6:56 pm |
|
|
|
Guest
|
Good day,
nm> are there any really fast ways to remove last element from list?
nm>
nm> list size is 5-15 elements, but it's not known at compile time.
nm>
nm> I need to implement something like FIFO, new elements inserted in list
nm> push old elements out.
Look at _queue_ module in standard distribution.
Best Regards,
Vladimir Sekissov
nm> Hi all!
nm>
nm> are there any really fast ways to remove last element from list?
nm>
nm> list size is 5-15 elements, but it's not known at compile time.
nm>
nm> I need to implement something like FIFO, new elements inserted in list
nm> push old elements out.
nm>
nm> now it looks line
nm> NewList = [ Elem | lists:sublist(List, N-1)]
nm>
nm> which probably is not the best way.
nm>
nm> --
nm> Gaspar Chilingarov
nm> System Administrator
nm>
nm> t +37491 419763
nm> w www.web.am
nm> e nm@web.am
nm>
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| asergey |
| Posted: Wed May 25, 2005 6:57 pm |
|
|
|
User
Joined: 12 Mar 2005
Posts: 313
|
You can either use the stdlib's queue module or look at the user's
contribution of double ended queues:
http://erlang.org/user.html#deque-1.0
Serge
Gaspar Chilingarov wrote:
> Hi all!
>
> are there any really fast ways to remove last element from list?
>
> list size is 5-15 elements, but it's not known at compile time.
>
> I need to implement something like FIFO, new elements inserted in list
> push old elements out.
>
> now it looks line
> NewList = [ Elem | lists:sublist(List, N-1)]
>
> which probably is not the best way.
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| ok at cs.otago.ac.nz |
| Posted: Thu May 26, 2005 7:27 am |
|
|
|
Guest
|
Gaspar Chilingarov <nm@web.am> wrote:
are there any really fast ways to remove last element from list?
No. However, there _is_ the standard "functional" representation for
queues:
hi_add(X, {L,R}) -> {[X|L],R}.
hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).
lo_add(X, {L,R}) -> {L,[X|R]}.
lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).
q_len({L,R}) -> length(L) + length(R).
q_empty({[],[]}) -> true;
q_empty(_) -> false.
I need to implement something like FIFO,
new elements inserted in list push old elements out.
Use the data structure above. Use lo_add/2 to add new elements
Q1 = lo_add(Elem, Q0)
and hi_rem/2 to remove old elements
{Elem, Q1} = hi_rem(Q0)
Or of course you could use hi_add/2 to add and lo_rem/2 to remove.
This isn't constant time, but it is constant _average_ time when used
as a queue. You do O(1) work to add an element and O(1) work *per element*
to reverse the list, although the peak cost per removal is O(|q_len|).
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| raimo at erix.ericsson.se |
| Posted: Thu May 26, 2005 8:01 am |
|
|
|
Guest
|
The functionality from deque-1.0 has been incorporated in the
queue module since R9C, except that to keep the data structure
backwards compatible; the length data field had to be left out.
So e.g the queue:len() operation runs in O(N) instead of O(1).
Maybe some other odd operations also are affected by this
missing field.
serge@hq.idt.net (Serge Aleynikov) writes:
> You can either use the stdlib's queue module or look at the user's
> contribution of double ended queues:
>
> http://erlang.org/user.html#deque-1.0
>
> Serge
>
> Gaspar Chilingarov wrote:
> > Hi all!
> > are there any really fast ways to remove last element from list?
> > list size is 5-15 elements, but it's not known at compile time.
> > I need to implement something like FIFO, new elements inserted in
> > list push old elements out.
> > now it looks line
> > NewList = [ Elem | lists:sublist(List, N-1)]
> > which probably is not the best way.
>
--
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| ok at cs.otago.ac.nz |
| Posted: Thu May 26, 2005 8:01 am |
|
|
|
Guest
|
Whoops.
hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).
should be
hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem({reverse([X|R]),[]}).
and
lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).
should be
lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem({[], reverse([X|L])}).
Untested code, OK? I hope the idea was clear anyway.
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| raimo at erix.ericsson.se |
| Posted: Thu May 26, 2005 8:34 am |
|
|
|
Guest
|
That is a good implementation of a fifo queue. In fact it is
the one the queue module in Erlang/OTP uses :-)
ok@cs.otago.ac.nz (Richard A. O'Keefe) writes:
> Gaspar Chilingarov <nm@web.am> wrote:
> are there any really fast ways to remove last element from list?
>
> No. However, there _is_ the standard "functional" representation for
> queues:
>
> hi_add(X, {L,R}) -> {[X|L],R}.
>
> hi_rem({[X|L],R}) -> {X, {L,R}};
> hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).
>
> lo_add(X, {L,R}) -> {L,[X|R]}.
>
> lo_rem({L,[X|R]}) -> {X, {L,R}};
> lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).
>
> q_len({L,R}) -> length(L) + length(R).
>
> q_empty({[],[]}) -> true;
> q_empty(_) -> false.
>
> I need to implement something like FIFO,
> new elements inserted in list push old elements out.
>
> Use the data structure above. Use lo_add/2 to add new elements
> Q1 = lo_add(Elem, Q0)
> and hi_rem/2 to remove old elements
> {Elem, Q1} = hi_rem(Q0)
> Or of course you could use hi_add/2 to add and lo_rem/2 to remove.
>
> This isn't constant time, but it is constant _average_ time when used
> as a queue. You do O(1) work to add an element and O(1) work *per element*
> to reverse the list, although the peak cost per removal is O(|q_len|).
>
--
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| klacke |
| Posted: Thu May 26, 2005 11:24 am |
|
|
|
User
Joined: 28 Feb 2005
Posts: 138
|
On Thu, May 26, 2005 at 09:55:27AM +0200, Raimo Niskanen wrote:
> That is a good implementation of a fifo queue. In fact it is
> the one the queue module in Erlang/OTP uses :-)
It is good.
The technique if amortizing the cost of an operation such as
removing the last item of a queue and sort of "remember the previous
work" can be used on many datastructures.
Chris Okasaki wrote an entire book on that topic.
http://www.amazon.co.uk/exec/obidos/ASIN/0521663504/qid=1117104079/sr=1-1/ref=sr_1_0_1/026-4716218-1856429
Most of the code in the Okasaki book amortize the cost of reversal of
lists. The same idea can sometimes be applied to integer arithmetcs
as well. Look at user contrib http://www.erlang.org/user.html#*beep*-1.0
/klacke
--
Claes Wikstrom -- Caps lock is nowhere and
http://www.hyber.org -- everything is under control
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
 
|
| ok at cs.otago.ac.nz |
| Posted: Thu May 26, 2005 4:52 pm |
|
|
|
Guest
|
Gaspar Chilingarov <nm@web.am> wrote:
are there any really fast ways to remove last element from list?
No. However, there _is_ the standard "functional" representation for
queues:
hi_add(X, {L,R}) -> {[X|L],R}.
hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).
lo_add(X, {L,R}) -> {L,[X|R]}.
lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).
q_len({L,R}) -> length(L) + length(R).
q_empty({[],[]}) -> true;
q_empty(_) -> false.
I need to implement something like FIFO,
new elements inserted in list push old elements out.
Use the data structure above. Use lo_add/2 to add new elements
Q1 = lo_add(Elem, Q0)
and hi_rem/2 to remove old elements
{Elem, Q1} = hi_rem(Q0)
Or of course you could use hi_add/2 to add and lo_rem/2 to remove.
This isn't constant time, but it is constant _average_ time when used
as a queue. You do O(1) work to add an element and O(1) work *per element*
to reverse the list, although the peak cost per removal is O(|q_len|).
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| ok at cs.otago.ac.nz |
| Posted: Thu May 26, 2005 4:53 pm |
|
|
|
Guest
|
Whoops.
hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).
should be
hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem({reverse([X|R]),[]}).
and
lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).
should be
lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem({[], reverse([X|L])}).
Untested code, OK? I hope the idea was clear anyway.
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| raimo at erix.ericsson.se |
| Posted: Thu May 26, 2005 4:57 pm |
|
|
|
Guest
|
The functionality from deque-1.0 has been incorporated in the
queue module since R9C, except that to keep the data structure
backwards compatible; the length data field had to be left out.
So e.g the queue:len() operation runs in O(N) instead of O(1).
Maybe some other odd operations also are affected by this
missing field.
serge@hq.idt.net (Serge Aleynikov) writes:
> You can either use the stdlib's queue module or look at the user's
> contribution of double ended queues:
>
> http://erlang.org/user.html#deque-1.0
>
> Serge
>
> Gaspar Chilingarov wrote:
> > Hi all!
> > are there any really fast ways to remove last element from list?
> > list size is 5-15 elements, but it's not known at compile time.
> > I need to implement something like FIFO, new elements inserted in
> > list push old elements out.
> > now it looks line
> > NewList = [ Elem | lists:sublist(List, N-1)]
> > which probably is not the best way.
>
--
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| raimo at erix.ericsson.se |
| Posted: Thu May 26, 2005 5:13 pm |
|
|
|
Guest
|
That is a good implementation of a fifo queue. In fact it is
the one the queue module in Erlang/OTP uses :-)
ok@cs.otago.ac.nz (Richard A. O'Keefe) writes:
> Gaspar Chilingarov <nm@web.am> wrote:
> are there any really fast ways to remove last element from list?
>
> No. However, there _is_ the standard "functional" representation for
> queues:
>
> hi_add(X, {L,R}) -> {[X|L],R}.
>
> hi_rem({[X|L],R}) -> {X, {L,R}};
> hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).
>
> lo_add(X, {L,R}) -> {L,[X|R]}.
>
> lo_rem({L,[X|R]}) -> {X, {L,R}};
> lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).
>
> q_len({L,R}) -> length(L) + length(R).
>
> q_empty({[],[]}) -> true;
> q_empty(_) -> false.
>
> I need to implement something like FIFO,
> new elements inserted in list push old elements out.
>
> Use the data structure above. Use lo_add/2 to add new elements
> Q1 = lo_add(Elem, Q0)
> and hi_rem/2 to remove old elements
> {Elem, Q1} = hi_rem(Q0)
> Or of course you could use hi_add/2 to add and lo_rem/2 to remove.
>
> This isn't constant time, but it is constant _average_ time when used
> as a queue. You do O(1) work to add an element and O(1) work *per element*
> to reverse the list, although the peak cost per removal is O(|q_len|).
>
--
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| nm at web.am |
| Posted: Thu May 26, 2005 6:31 pm |
|
|
|
Guest
|
Thanks to all.
I got the point and it was the same what I suspect - there
is no way to avoiding reversing list :)
--
Gaspar Chilingarov
System Administrator
t +37491 419763
w www.web.am
e nm@web.am
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| wuji |
| Posted: Thu Aug 23, 2012 6:22 am |
|
|
|
User
Joined: 10 Aug 2012
Posts: 654
|
class passengers, crew members and government employees flying from Amsterdam Amsterdam cheap Ralph Lauren Polo Amsterdam to the United States.At least one batch of 17
appeared to be made by a U.S. company based at at [h1]replica designer bags for sale[/h1] at Amsterdam's Schiphol airport. Those sandwiches were served board Delta's
to Minneapolis-St. Paul Sunday afternoon. Two passengers aboard the flight flight [h4]designer replica *beep*[/h4] flight found needles in their sandwiches, officials confirmed. The sandwiches
turned over by Delta to Customs and Border Patrol.Two passengers passengers [h2]cheap louboutins[/h2] passengers sustained minor injuries after biting into the sandwiches and
officials found a third needle after confiscating the sandwiches, according according [h3]cheap polo shirts[/h3] according to an official report."Delta is taking this matter extremely
and is cooperating with local and federal authorities who are are [h3]cheap polo shirts[/h3] are investigating the incident," Delta spokeswoman Kristin Bauer said in |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
