How can I use randsample in Matlab without running out of memory?

user_9947624 0
Viewed 197

I want to sample without replacement m integers between 1 and n in Matlab, where

m=10^6;
p=13^5;
n=p*(p-1)/2;

I have tried to use randsample as follows

random_indices_pairs=randsample(n,m);

However, I get a memory issue which is

    Error using zeros
    Requested 1x68929060278 (513.6GB) array exceeds maximum array size preference. Creation of arrays greater than this
    limit may take a long time and cause MATLAB to become unresponsive. See array size limit or preference panel for more
    information.

Error in randsample (line 149)
                x = zeros(1,n); % flags

Is there a way to avoid that? The issue here is due to the fact that n is huge.

matlab random
3 Answers

The two-input version of randperm is equivalent to randsample without replacement, and doesn't have memory issues:

random_indices_pairs = randperm(n, m);
user_25869220

Below script should do what you're looking for.

  • It first picks m random integers in the range 1 to n.
  • Then it checks if there are any duplicate entries
  • If not, the script stops
  • If there are duplicate entries:
    • it goes through all of them
    • finds another random number between 1 and n
    • checks if that new random number exists in the array of integers
      • if it does, it finds another random number
      • if it doesn't, it replaces the duplicate in the array and moves on to the next duplicate
%% Initialize
clearvars;
clc;

m = 10e6;
p = 13e5;
n = p*(p-1)/2;

%% Create m random integers between 1 and n
randomInt = randi(n, m, 1);

%% Find indices where duplicate random integers are
% Find indices of unique values, take the index of the first occurrence
[~, I] = unique(randomInt, 'first');
% Generate an array of all indices
dupIdx = 1:length(randomInt);
% Drop indices which point to the first occurrence of the duplicate
% This leaves indices that point to the duplicate
dupIdx(I) = [];
% Free up some memory
clear I;

if isempty(dupIdx)
    disp('Done!')
else
    % For those indices find another random number, not yet in randomInt
    disp('Found duplicates, finding new random numbers for those')
    counter = 0;
    for ii = dupIdx
        counter = counter + 1;
        disp(strcat("Resolving duplicate ", num2str(counter), "/", num2str(length(dupIdx))))
        dupe = true;
        % While the replacement is already in the randomInt array, keep
        % looking for a replacement
        while dupe
            replacement = randi(n, 1);
            if ~ismember(replacement, randomInt)
                % When replacement is unique in randomInt
                % Put replacement in the randomInt array at the right index
                randomInt(ii) = replacement;
                dupe = false;
            end
        end
    end
end
user_12563470

Based on one of the comments (the comment suggests also possible improvements).

A=randi(n,m,1);
[U, I] = unique(A, 'stable');
A=A(I);
m_to_add=m-size(A,1);

while m_to_add>0
      B=randi(n,m_to_add,1);
      A=[A;B];
      [U, I] = unique(A, 'stable');
      A=A(I);
      m_to_add=m-size(A,1);
end
user_99476240
Related