Stack Overflow
Stack Overflow

Questions tagged [space-efficiency]

67 questions
135
votes
3 answers

Difference between passing array and array pointer into function in C

What is the difference between the two functions in C? void f1(double a[]) { //... } void f2(double *a) { //... } If I were to call the functions on a substantially long array, would these two functions behave differently, would they take…
Kaushik Shankar
  • 5,491
  • 4
  • 30
  • 36
40
votes
4 answers

Is Quicksort in-place or not?

So the space efficiency of Quicksort is O(log(n)). This is the space required to maintain the call stack. Now, according to the Wikipedia page on Quicksort, this qualifies as an in-place algorithm, as the algorithm is just swapping elements within…
Akeenan
  • 501
  • 1
  • 5
  • 5
39
votes
7 answers

What is the most efficient binary to text encoding?

The closest contenders that I could find so far are yEnc (2%) and ASCII85 (25% overhead). There seem to be some issues around yEnc mainly around the fact that it uses an 8-bit character set. Which leads to another thought: is there a binary to text…
Mark
13
votes
16 answers

Most compact way to encode a sequence of random variable length binary codes?

Let's say you have a List> and you want to encode that into binary form in the most compact way possible. I don't care about read or write performance. I just want to use the minimal amount of space. Also, the example is in Java, but…
Pyrolistical
  • 27,624
  • 21
  • 81
  • 106
10
votes
5 answers

C# Array slice without copy

I'd like to pass a sub-set of a C# array to into a method. I don't care if the method overwrites the data so would like to avoid creating a copy. Is there a way to do this? Thanks.
user1400716
  • 1,126
  • 5
  • 13
  • 32
9
votes
4 answers

more efficient way to pickle a string

The pickle module seems to use string escape characters when pickling; this becomes inefficient e.g. on numpy arrays. Consider the following z = numpy.zeros(1000, numpy.uint8) len(z.dumps()) len(cPickle.dumps(z.dumps())) The lengths are 1133…
gatoatigrado
  • 16,580
  • 18
  • 81
  • 143
7
votes
6 answers

Algorithms for Big O Analysis

What all algorithms do you people find having amazing (tough, strange) complexity analysis in terms of both - Resulting O notation and uniqueness in way they are analyzed?
VarunGupta
  • 6,127
  • 5
  • 27
  • 31
6
votes
3 answers

RSync single (archive) file that changes every time

I am working on an open source backup utility that backs up files and transfers them to various external locations such as Amazon S3, Rackspace Cloud Files, Dropbox, and remote servers through FTP/SFTP/SCP protocols. Now, I have received a feature…
Michael van Rooijen
  • 6,683
  • 5
  • 37
  • 33
6
votes
3 answers

Java Byte/byte array space efficiency comparison

I need to create a space efficient 2D array for a large number of 8 bit values. I began writing my class using a few layers of abstraction and generics to allow for code reuse. Once I got to implementing the concrete class it occurred to me I cannot…
recursion.ninja
  • 5,377
  • 7
  • 46
  • 78
5
votes
3 answers

Initiate a float list with zeros in C#

I want to initiate a list of N objects with zeros( 0.0 ) . I thought of doing it like that: var TempList = new List(new float[(int)(N)]); Is there any better(more efficeint) way to do that?
axcelenator
  • 1,497
  • 3
  • 18
  • 42
5
votes
1 answer

New user email verification code (Best practices)

I have been studying the best practices are for email verification of a user who is trying to register on a site. (I am running a laravel installation and this is happening in php, though this is more of a theoretical question). I have a few…
Sainath Krishnan
  • 2,089
  • 7
  • 28
  • 43
5
votes
4 answers

List of maps: efficient implementations

I have code that creates and uses a collection such as: List> tableData; This list of maps gets populated with n maps each representing one row in a database. Each row is represented as a map between the field name and the…
Giovanni Botta
  • 9,626
  • 5
  • 51
  • 94
4
votes
1 answer

Efficient way to store 3D normal vector using two floats

I need to store 3D normal vectors, that is vectors (x, y, z) such that x^2 + y^2 + z^2 = 1. But due to space constraints I can only use 2 floats to store it. So by storing only x and y, the third component can be computed as sqrt(1 - x^2 - y^2),…
tmlen
  • 8,533
  • 5
  • 31
  • 84
4
votes
7 answers

Efficiently finding the ranks of elements in an array?

How does one find the rank of each element of an array, averaging in the case of ties, efficiently? For example: float[] rank(T)(T[] input) { // Implementation } auto foo = rank([3,6,4,2,2]); // foo == [3, 5, 4, 1.5, 1.5] The only way I can…
dsimcha
  • 67,514
  • 53
  • 213
  • 334
4
votes
1 answer

Is there a space efficient implementation of mergesort?

I just coded up this working version of mergesort: static int[] merge(int[] first, int[] second){ int totalsize = first.length + second.length; int[] merged_array = new int[totalsize]; int i = 0, firstpointer = 0, secondpointer = 0; …
ElectronAnt
  • 2,115
  • 7
  • 22
  • 39
1
2 3 4 5