Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have data in the following form. I have a list of values and a list of frequencies that indicate how often each value has occurred.

Example list of values: {5,7,4}

Example list of frequencies: {1,2,3}

I would like to obtain the original data from which such a histogram was generated. Any suggestions on how to do this with Mathematica ?

Example: {5,7,7,4,4,4}

share|improve this question

3 Answers 3

up vote 15 down vote accepted

Without looking at performance, but only on understanding: First, you create a function f which takes a value and a count and which reproduces the value exactly count times. In the simplest case

f[val_, count_] := ConstantArray[val, count]

and you can call f[3,4] to get {3,3,3,3}. Now, you combine your input arrays so that you can call f directly for each pair. For this, you can use MapThread. To create you final result, you have to Flatten the output:

Flatten[MapThread[f, {{5, 7, 4}, {1, 2, 3}}]]

This all can of course be combined into one call

vals = {5, 7, 4};
counts = {1, 2, 3};

Flatten[MapThread[ConstantArray, {vals, counts}]]

or

ConstantArray @@@ Transpose[{vals, counts}] // Flatten

or (to simplify kgulers approach)

Inner[ConstantArray, vals, counts, Join]

and many more

share|improve this answer
 values = RandomSample[Range[100], 5]
 (*{72,75,44,25,60}*)
 counts = RandomInteger[{1, 5}, 5]
 (* {4,3,1,1,1} *)

Inner and Table:

 Inner[Table[#1, {#2}] &, values, counts, Join] (*thanks: Halirutan *)

Inner and ConstantArray:

 Flatten@Inner[ConstantArray, values, counts, List]

both give

 {72, 72, 72, 72, 75, 75, 75, 44, 25, 60}

Update: further variations using Thread, MapIndexed ...

 Table @@@ Thread[{values, List /@ counts}] // Flatten
 #1[[Join @@ MapIndexed[Table[First[#2], {#}] &, #2]]] &[values, counts]
 Module[{f}, Thread[f[values, List /@ counts]] /. f -> Table // Flatten]
share|improve this answer

Introduction

This answer is mainly concerned with the performance (speed and memory) of methods that solve the OPs problem. Of course we only care about performance if the data of some considerable size. In this answer I first generate data, then show some methods to solve the problem and then I compare the timings.

Generating data: Similarity to data from FactorInteger

Let's generate some data to do timing comparisons with. Let us first realise that there is another setting in which the same problem can occur. Suppose one wants to find a list of all the prime factors of an integer. FactorInteger does almost exactly this job, but instead repeating prime numbers that occur more than once as a factor, it gives the number of the times the factor occurs in the factorisation.

To get from FactorInteger to data that matches this problem, we would have to do

in=10012312312312;
{values, counts} = {sortedUniquePrimes, primeTimes} = Transpose@FactorInteger[in]

However, the length of prime factorisation of a (uniformly) random integer is a bit chaotic. Therefore I make the data corresponding to prime factorisations in a different manner.

Note that there is an extremely small probability that there will be an error in generating the data, in which case you can just execute the code again. The data below is not large enough to justify e.g. creating a library (as we will see being created in one of the methods below), but it is large enough to compare the methods sensibly.

Block[{primes, primeSeeds},
 primes = Table[Prime[kkkk], {kkkk, 500000}]; 
 primeSeeds = RandomInteger[{1, 500000}, 2000000];
 sortedUniquePrimes = 
  Take[DeleteDuplicates[Sort[Part[primes, primeSeeds]]], 200000];
 primeTimes = RandomInteger[{1, 10}, 200000];
 ]

Methods

The fastest thing I could come up with was a function written in C that was linked to the kernel by LibraryLink. A compiled function turned out to be pretty fast as well. I programmed some funky code making use of Span, but that turned out to be slower than Halirutans version. It seems that Span is best used when one only has to change a part of a list.

LibraryLink function

There are three things I can think that may make you want to not execute the following code. One is that if you do not have a C compiler, this is not going to work. Another thing is that I do not clean up the library after creating it, which is probably not a big deal, but still. A third thing is that it may crash the kernel (this version never crashed for me), as it is one of my first programs written for LibraryLink.

Here is the function (in fact the entire file) written in C

#include "WolframLibrary.h"

/* Return the version of Library Link */
DLLEXPORT mint WolframLibrary_getVersion( ) {
    return WolframLibraryVersion;
}

/* Initialize Library */
DLLEXPORT int WolframLibrary_initialize( WolframLibraryData libData) {
    return LIBRARY_NO_ERROR;
}

/* Uninitialize Library */
DLLEXPORT void WolframLibrary_uninitialize( WolframLibraryData libData) {
    return;
}

DLLEXPORT int converter_TT_T(WolframLibraryData libData, mint Argc, MArgument *Args, MArgument Res) {
    MTensor result;

    int err = LIBRARY_NO_ERROR;

    MTensor valueTensor;
    MTensor frequencyTensor;
    mint *valueDataPtr;
    mint *frequencyDataPtrHard;
    mint *frequencyDataPtr;

    mint *resultDataPtr;

    mint valueDataDim;
    mint frequencyDataDim;

    valueTensor = MArgument_getMTensor(Args[0]);
    frequencyTensor = MArgument_getMTensor(Args[1]);

    valueDataPtr = libData->MTensor_getIntegerData(valueTensor);
    frequencyDataPtrHard = libData->MTensor_getIntegerData(frequencyTensor);
    frequencyDataPtr = frequencyDataPtrHard;

    valueDataDim = * libData->MTensor_getDimensions(valueTensor);
    frequencyDataDim = * libData->MTensor_getDimensions(frequencyTensor);


    if(valueDataDim != frequencyDataDim) goto error_label;

    mint iiii;
    mint total = 0;

    for(iiii = 0; iiii < valueDataDim; iiii++)
    {
        total += *frequencyDataPtr;
        frequencyDataPtr++;
    }

    err = libData->MTensor_new(MType_Integer, 1, &total, &result);
    if(err) goto error_label;

    resultDataPtr = libData->MTensor_getIntegerData(result);

    frequencyDataPtr = frequencyDataPtrHard;

    mint jjjj;
    mint freq;

    for(iiii = 0; iiii < valueDataDim; iiii++)
    {
        jjjj = 1;
        freq = *frequencyDataPtr;
        while(jjjj <= freq){
            *resultDataPtr = *valueDataPtr;
            resultDataPtr++;
            jjjj++;
        }

        valueDataPtr++;
        frequencyDataPtr++;
    }

    libData->MTensor_disown(valueTensor);
    libData->MTensor_disown(frequencyTensor);

    MArgument_setMTensor(Res, result);
    return err;

    error_label:
    libData->MTensor_disown(valueTensor);
    libData->MTensor_disown(frequencyTensor);
    if(!err) err = 1;
    return err; 

}

This function can be linked to the kernel as follows. Save the code above (and nothing more, you don't need a function main or something like that) in a file name.c at the path path (in a folder to which path points). Then execute the following code, after filling in the first two lines.

path = (*input your path here*)   ;
cFileName = (*input the name of your file (example: "name.c") here *)   ;

libraryName = "libraryName"

<< SymbolicC`
<< CCodeGenerator`
<< Developer`
SetDirectory[path];

(*if you execute the command `CreateLibrary` below more than once, make sure to specify a
new libraryName *)

lib = CreateLibrary[{cFileName}, libraryName] (*no extension needed for libraryName*)

converterLL = 
 LibraryFunctionLoad[libraryName, 
  "converter_TT_T", {{Integer, 1, "Shared"}, {Integer, 1, 
    "Shared"}}, {Integer, 1}]

To test if the function has loaded successfully, you can now simply try feeding it some data

converterLL[{1, 2, 3, 4, 5, 6} // ToPackedArray, {1, 2, 1, 1, 1, 2} //
   ToPackedArray]

which should evaluate to

{1, 2, 2, 3, 4, 5, 6, 6}

Note that the lengths of the arrays that are given as arguments to converterLL should be of equal length. Otherwise an error is thrown corresponding to err = 1 in LibraryLink. err = 1 is supposed to correspond to a type error, so don't be fooled by this.

Compiled function

The compiled function is really similar to the function written in C. This function does not calculate the total of the list of frequencies, unlike the function written in C. In C I access arrays using pointers, whereas here I use Part, e.g. in factors[[jjjj]]. Compiling with CompilationTarget->"C" makes this about 4 times as fast the result without this option.

cfu =
 Compile[
  {{primeTimes, _Integer, 1}, {factors, _Integer, 
    1}, {tot, _Integer}, {nPrimes, _Integer}}
  ,
  Block[{res, kkkk, fac},
   res = ConstantArray[0, tot];
   kkkk = 0;
   Do[
    fac = factors[[jjjj]];
    Do[
     kkkk++;
     res[[kkkk]] = fac
     ,
     {primeTimes[[jjjj]]}
     ]
    ,
    {jjjj, nPrimes}
    ];
   res
   ]
   ,CompilationTarget-> "C"
  ]

Other methods

One of the functions using Span below has Part as a local variable in Block. This is not really necessary and it may cause problems when you are using dynamics. But I suppose it keeps things funky.

initWSpanList[] := 
 (
  occurrences = Accumulate@primeTimes;
  tot = Last@occurrences;
  spanList = 
   Span @@@ 
    Transpose[{Prepend[Delete[occurrences, -1], 0] + 1, 
      occurrences}];
  )

span1[] :=
  Block[{occurrences, tot, spanList, res1, applyFoodRes1},
   initWSpanList[];
   res1 = ConstantArray[0, tot];
   applyFoodRes1 = Transpose[{spanList, sortedUniquePrimes}];
   Function[res1[[#1]] = #2] @@@ applyFoodRes1;
   res1
   ];

span2[] :=
  Block[{occurrences, tot, spanList, applyFoodRes1},
   initWSpanList[];
   res2 = ConstantArray[0, tot];
   ReleaseHold@
    Block[
     {res2, Part}, 
     Hold[Set][Hold@Evaluate[res2[[#]] & /@ spanList], 
      sortedUniquePrimes]
     ];
   res2
   ];

Functions for tidyness and comparison

inner[] := Inner[ConstantArray, sortedUniquePrimes, primeTimes, Join]

compiled[] := cfu[primeTimes, sortedUniquePrimes, Total@primeTimes, 
        Length@sortedUniquePrimes];

libLink[] := converterLL[sortedUniquePrimes, primeTimes];

Timing Comparisons

<< Developer`
(res1 = span1[]) // Timing // First
(res2 = span2[]) // Timing // First
(res3 = inner[]) // Timing // First
(res4 = compiled[]) // Timing // First
(res5 = libLink[]) // Timing // First

TrueQ[res1 == res2 == res3 == res4 == res5]
PackedArrayQ /@ {res1, res2, res3, res4, res5}
{Length@res1, Total@primeTimes}

0.497182
0.410232
0.152209
0.020913
0.003353
True
{True, True, True, True, True}
{1100332, 1100332}

share|improve this answer
    
Am I really dumb or is this an answer to another question? –  s0rce Nov 28 '13 at 16:31
    
@s0rce ah well you should read vals == sortedUniquePrimes and counts == primeTimes. Then you will see that my res3 is generated by halirutans code. I'm sorry it was indeed going to be a separate self answered Q&A, but then I found this question and I felt it was too similar to make a new Q&A. The data was generated with a different idea in mind, but really its the same thing. Maybe my adaptations were insufficient. –  Jacob Akkerboom Nov 28 '13 at 16:43
    
Another note: We can probably avoid two rewrites of the entire array if we use librarylink, as we do not have to initialize all the elements of the tensor to 0 (which ConstantArray does do). –  Jacob Akkerboom Nov 28 '13 at 17:56
    
@s0rce I have updated the answer, perhaps you wanna have another go at it? –  Jacob Akkerboom Nov 29 '13 at 16:45
    
@Kuba I suppose now my answers really look like they weren't written in Mathematica :P. Except that I somehow load the package SymbolicC` for no reason :P –  Jacob Akkerboom Nov 29 '13 at 19:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.