Geek Answers Handbook

Java - Returns the random index of a specific character in a string

Therefore, for a string such as:, 0100101I want to return a random unit index of one of the positions a 1(1, 5, 6).

So far I am using:

protected int getRandomBirthIndex(String s) {
        ArrayList<Integer> birthIndicies = new ArrayList<Integer>();
        for (int i = 0; i < s.length(); i++) {
            if ((s.charAt(i) == '1')) {
                birthIndicies.add(i);
            }
        }
        return birthIndicies.get(Randomizer.nextInt(birthIndicies.size()));
    }

However, this causes a bottle on my code (45% of the processor time in this method), since the strings are longer than 4000 characters. Can anyone think of a more efficient way to do this?

+4
source share
6 answers

If you are interested in one index of one of the positions with 1and suppose that there is at least one at your input 1, you can simply do this:

    String input = "0100101"; 
    final int n=input.length();
    Random generator = new Random();
    char c=0;
    int i=0;
    do{
        i = generator.nextInt(n);           
        c=input.charAt(i);
    }while(c!='1');
    System.out.println(i);

, , 1 0 . @paxdiablo, , , 1 .

+1

String.indexOf(int), 1 ( ). List <>. - ,

private static Random rand = new Random();
protected int getRandomBirthIndex(String s) {
    List<Integer> birthIndicies = new ArrayList<>();
    int index = s.indexOf('1');
    while (index > -1) {
        birthIndicies.add(index);
        index = s.indexOf('1', index + 1);
    }
    return birthIndicies.get(rand.nextInt(birthIndicies.size()));
}

, , List ( ). , memoization,

private static Random rand = new Random();
private static Map<String, List<Integer>> memo = new HashMap<>();

protected int getRandomBirthIndex(String s) {
    List<Integer> birthIndicies;
    if (!memo.containsKey(s)) {
        birthIndicies = new ArrayList<>();
        int index = s.indexOf('1');
        while (index > -1) {
            birthIndicies.add(index);
            index = s.indexOf('1', index + 1);
        }
        memo.put(s, birthIndicies);
    } else {
        birthIndicies = memo.get(s);
    }
    return birthIndicies.get(rand.nextInt(birthIndicies.size()));
}
+1

, , , , , . , .

, , , :

  • ;
  • ;
  • .

, , , . - .

getRandomBirthIndex() ( ) :

  • , , , .
  • .

, , , .

- :

# Constructs fastie from string.
# Sets cached string to something other than
# that passed in (lazy list creation).

def fastie.constructor(string s):
    me.current = s
    me.cached = s + "!"

# Changes current string in fastie. No list update in
# case you change it again before needing an element.

def fastie.changeString(string s):
    me.current = s

# Get a random index, will recalculate list first but
# only if necessary. Empty list returns index of -1.

def fastie.getRandomBirthIndex()
    me.recalcListFromCached()
    if me.list.size() == 0:
        return -1
    return me.list[random(me.list.size())]

# Recalculates the list from the current string.
# Done on an as-needed basis.

def fastie.recalcListFromCached():
    if me.current != me.cached:
        me.cached = me.current
        me.list = empty
        for idx = 0 to me.cached.length() - 1 inclusive:
            if me.cached[idx] == '1':
                me.list.append(idx)

1, , indexOf(), Java, (-, ):

def fastie.recalcListFromCached():
    if me.current != me.cached:
        me.cached = me.current
        me.list = empty
        idx = me.cached.indexOf('1')
        while idx != -1:
            me.list.append(idx)
            idx = me.cached.indexOf('1', idx + 1)

, . , Java- , .

, 45% . , , .

, , , , , , 0,001 ( ). , . .

+1

, , 1 ( , ), , , "" , , . , , :

String s = "0100101";
int index = ThreadLocalRandom.current().nextInt(s.length());

while(s.charAt(index) != '1') {
    System.out.println("got not a 1, trying again");
    index = ThreadLocalRandom.current().nextInt(s.length());
}
System.out.println("found: " + index + " - " + s.charAt(index));

, , , . .

Source-String , !

0

O(1), O(n), - , Randomizer, .

private static Random rand = new Random(); 
protected int getRandomBirthIndex(String s) {
    List<Integer> birthIndicies = new ArrayList<>();
    int index = s.indexOf('1');
    while (index > -1) {
        birthIndicies.add(index);
        index = s.indexOf('1', index + 1);
    }
    return birthIndicies.get(rand.nextInt(birthIndicies.size())); 
}
0

Fisher-Yates shuffle. indices . , . , indices, , , -1.

, indices static, , . , indices . 7, , 0100101.

// delete this and uncomment below if string lengths vary
private static int[] indices = { 0, 1, 2, 3, 4, 5, 6 };

protected int getRandomBirthIndex(String s) {
   int tmp;
   /*
    * int[] indices = new int[s.length()];
    * for (int i = 0; i < s.length(); ++i) indices[i] = i;
    */
   for (int i = 0; i < s.length(); i++) {
      int j = randomizer.nextInt(indices.length - i) + i;
      if (j != i) {   // swap to shuffle
         tmp = indices[i];
         indices[i] = indices[j];
         indices[j] = tmp;
      }
      if ((s.charAt(indices[i]) == '1')) {
         return indices[i];
      }
   }
   return -1;
}

This approach ends quickly if 1 is dense, guarantees completion after s.length()iterations, even if there are none, and the returned locations are uniform in many units.

0
source

More articles:


All Articles