# Tag Info

28

Assuming that you mean "integer" when you say "number", you can use a bitvector of size 2^n, where n is the number of elements (say your range includes integers between 1 and 256, then you can use an 256-bit, or 32 byte, bitvector). When you come across an integer in position n of your range, set the nth bit. When you're done enumerating the collection of ...

24

I'll expand my comment: ... if you're adding or removing elements, you want a list (or other flexible data structure). Arrays are only really good when you know exactly how many elements you need at the start. A Quick Breakdown Arrays are good when you have a fixed number of elements that is unlikely to change, and you wish to access it in a ...

18

Yes, there are such languages. Many of them. In fact, this feature is pretty much the definition of an array language or vector language. Examples of array and vector languages include, but are not limited to, the APL family of languages with its successors, derivatives and cousins (E.g. APL, J, K) and pretty much all mathematical and statistical languages ...

16

I'll expand my comment a bit. The List[T] data structure, from scala.collection.immutable is optimized to work the way an immutable list in a more purely functional programming language works. It has very fast prepend times, and it is assumed that you will be working on the head for almost all of your access. Immutable lists get to have very fast prepend ...

12

Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too. For example, this is a simple implementation of map and fold that take one list only: (define (map1 f l) (if (null? l) l (cons (f (car l)) (map1 f (cdr ...

11

How do you propose the head be reached in this reversed list? If not using mutable structures the reversed list would only be performant if you made the head linear time and tail constant. But now you've got the exact same structure as before except you're calling the head the tail and vice versa. the structure is the way it is because regardless of which ...

10

A generic queue or array is generally not, by itself, thread safe, just like many other data types. Thread safety is usually accomplished in two ways: Using mutex locks - each thread that wants to modify a value has to wait. Delegation - only the owning thread can modify the value. Mutex locks are fairly straight forward - nobody owns the value, but only ...

10

The most important factor is that you can prepend to an immutable singly linked list in O(1) time, which allows you to recursively build up n-element lists in O(n) time like this: // Build a list containing the numbers 1 to n: foo(0) = [] foo(n) = cons(n, foo(n-1)) If you did this using immutable arrays, the runtime would be quadratic because each cons ...

8

If by "best" you actually mean "fastest", then by far the fastest way (although not nearly the most efficient way) is to choose a multiplier that makes all of the weights integers, at least to whatever precision you care about, and then store that many copies of each in one large array. For example, if you assign "score multiplier" a weight of 80%, and ...

7

Consider the problem of manipulating a list into a different state where you know the end state. Find each 'enclosed subgraph' bigger than one (I'll explain this later on). Find the sum of the lengths of the subgraphs and subtract the number of subgraphs. There's your answer for the number of swaps. An 'enclosed subgraph' is a minimal subset of the whole ...

6

Even more, C++ have such functions, take a look to algorithm (or with C++11 additions) header: std::transform std::for_each std::remove_copy_if They can be easily used with any container. For example your code can be expressed like this (with C++11 lambdas for easy coding): std::vector<int> x = {1, 2, 3, 4, 5}; std::vector<int> y; ...

6

Python actually supports insertion of arbitrary sub-lists, as a part of list slice assignment. You just assign to an empty slice before the element where you want to insert a new list: list1 = [1, 2, 3] list1[1:1] = [10, 20, 30] # insert 3 elements at index 1 print list1 # prints [1, 10, 20, 30, 2, 3] Many languages view lists as primarily sequential ...

4

If you sort the entire list first, then you guarantee worst-case run-time. Also, your choice of sort algorithm is critical. Here's how I'd approach this problem: Use a heap sort, focusing on the smallest elements in the list. After each swap, see if you have a gap. If you find a gap, then return: You have found your answer. If you don't find a gap, ...

4

I think it comes down to lists being rather easily implemented in functional code. Scheme: (define (cons x y)(lambda (m) (m x y))) Haskell: data [a] = [] | a : [a] Arrays are harder and not nearly as pretty to implement. If you want them to be extremely fast then they'll have to be written low-level. Additionally, recursion works much better on ...

4

If you are creating a class library to be shared with other .NET applications, and this is part of the public interface, then you should stick with normal .NET class library types. If you are sticking solely to the F# domain, or this is part of the private implementation details, I would prefer to use native F# types. In your case however, the F# list does ...

4

One common way to do this efficiently, at least in Haskell, is using a difference list which permit O(1) snoc, which is the inverse of cons (yes, it's a silly name). An alternative is not using linked lists in favor of a more appropriate data structure, such as finger trees (Data.Seq in Haskell, amortized constant time cons/snoc) or queues (there are ...

4

You are correct to avoid using the word index in the column name. I suggest that you avoid names that could be misinterpreted if you have a reasonable substitute. One option is to call the column "SortOrder" or "DisplayOrder". Is there a requirement for the list of items to be displayed or sorted in a particular order? If it's not required, you might save ...

4

The best way to approach this is to go to FP Complete's Hoogle and type in the signature you're looking for, (a -> Maybe b) -> [a] -> Maybe [b]. The first hit is a function called mapM which is exactly what you are looking for. In fact it works for all Monads, not just Maybe. (If you want to be even more general you can use traverse)

4

You want a function with this signature: (a -> Maybe b) -> [a] -> Maybe [b] Entering this into hoogle gives this possibility: Prelude mapM :: Monad m => (a -> m b) -> [a] -> m [b] A look at the Hackage documentation for mapM says it is the same as: mapM f = sequence . map f and that the definition of sequence is: sequence ...

3

"Write the most simple thing that could possibly work" is one principle, but it is not the only one, and it isn't always the most important one. "Don't repeat yourself" is arguably more important, and repeating yourself the way you describe is definitely not justified by "most simple". As soon as you notice repeating yourself, you should switch to a solution ...

3

@bytebuster made a comment above that got me to thinking. The .NET's Queue<T> is mutable, and undoubtedly has a standard OO implementation which has guaranteed O(1) for enqueue and dequeue. Okasaki's being the standard best-performance immutable functional version of a Queue and not having the same guarantee, perhaps you could apply this rule to your ...

3

Presenting the items of a list in the same order is strongly recommended for every GUI. However the ordering logic should be part of the presentation layer. Different users will have different orderings. This should be stored as a user preference. If you want a simpler solution just use a hardwired ordering, doesn't matter as long as you don't rely on ...

3

Because appending to the end of a linked list is O(n) and appending to the front is O(1). The operation you're looking for is called snoc and can be implemented. But inefficiently. To see why, realize that when you append to the back of a list, if you don't mutate anything, every single element must be copied, where as with appending to the front, you can ...

2

How about a simple selection sort ? Find the min(A C D Q R Z E) Swap if min() != first element Repeat with (C D Q R Z E) Count the number of swaps. On your example: ACD are already in order so no swap required. First swap required to put E in place R is min of QRZ, again swap to put it place Q is min of QZ, swap to put in place ... so simple without ...

2

What is the range of numbers you will encounter? If that range is not very large, you could solve this with two scans (linear time O(n)) using an array with as many elements as you have numbers, trading space for time. You could find the range dynamically with one more scan. To reduce space, you could assign 1 bit to each number, giving you 8 numbers ...

2

You can use Cons nodes easily only if you have a garbage collected language. Cons Nodes matche a lot with the functional programming style of recursive calls and immutable values. So it fits well into the mental programmer model. And don't forget historical reasons. Why are they still called Cons Nodes and worse still use car and cdr as accessors? People ...

2

Insertion itself is O(1) at the beginning of the list. (cons x '(world)) Inserts "x" at the beginning of the list containing world. If you have an array and you want to insert an element at the beginning, you have to shift everything over by one. Not so with lists!

2

Ok, so you are doing what you think is the simplest thing that works, but you haven't defined your problem adequately. Turn the problem around and look at what you have. "Implement a List clone" has many nuances to it which need to be expanded and documented. What is the purpose of this List clone? What number of items is it expected to support? Generally ...

2

As you say yourself, the best solution is to do the counting in the output, instead of storing it in the various lists. That way you don't have to store (and recalculate) the ranking numbers on each event for each (sub-)list, but you only calculate them when needed. For the "You are on position # in the ranking" text, you could have a method in the class ...

2

There may be minor performance considerations involved with it, but this sounds like the sort of thing LINQ is very useful for. The basic idea is this: var enormousList = new List<record>(); //var enormousList = ... (over 5 million records) var subList = enormousList.Where(onerecord => onerecord.clanName == "RAGIN CAJUN"); // At this point in the ...

Only top voted, non community-wiki answers of a minimum length are eligible