Article View: comp.lang.misc
Article #5694Re: Random permutation algorithm
From: robison
Date: Mon, 22 Aug 1988 18:25
Date: Mon, 22 Aug 1988 18:25
28 lines
1581 bytes
1581 bytes
The paper cited[1] deliberately specifies problems biased towards imperative
languages. The authors are asking if applicative languages are inherently
slower than imperative languages (in the asymptotic sense). Seven problems
were specified for which the known imperative solutions are faster than
the known applicative solutions. For example, another problem in the paper is:
Problem: Array Transactions
Description: Given n and sequence of k read/write operations to array
indexed 1,...,n, produce the sequence of results of the
read operations. Let k>n.
This is solvable in O(k) time on an imperative machine, but the best known
on an applicative machine is O(k log n). (The solution simulates the array
with an AVL tree.)
[1] Carl G. Ponder, Patrick C. McGeer, and Antony P-C. Ng,
"Are applicative languages inefficient?", SIGPLAN Notices,
vol. 23,6, June 1988, 135-139.
Arch D. Robison
University of Illinois at Urbana-Champaign
CSNET: robison@UIUC.CSNET
UUCP: {pur-ee,convex}!uiucdcs!robison
ARPA: robison@CS.UIUC.EDU (robison@UIUC.ARPA)
Technical Details
Message-ID:
<5200017@m.cs.uiuc.edu>Path:
arc1-ca.pugleaf.net!utzoo!attcan!uunet!lll-winken!lll-tis!ames!ncar!oddjob!uxc!uxc.cso.uiuc.edu!a.cs.uiuc.edu!m.cs.uiuc.edu!robisonReferences:
<5200012@m.cs.uiuc.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!lll-winken!lll-tis!ames!ncar!oddjob!uxc!uxc.cso.uiuc.edu!a.cs.uiuc.edu!m.cs.uiuc.edu!robison From: robison@m.cs.uiuc.edu Newsgroups: comp.lang.misc Subject: Re: Random permutation algorithm Message-ID: <5200017@m.cs.uiuc.edu> Date: 22 Aug 88 18:25:00 GMT References: <5200012@m.cs.uiuc.edu> Lines: 27 Nf-ID: #R:m.cs.uiuc.edu:5200012:m.cs.uiuc.edu:5200017:000:1097 Nf-From: m.cs.uiuc.edu!robison Aug 22 13:25:00 1988