Esiste un modo per eseguire loop nidificati di livello n in Java?
https://stackoverflow.com/questions/426878
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
In altre parole, posso fare qualcosa del genere
for() {
for {
for {
}
}
}
Tranne N volte? In altre parole, quando viene chiamato il metodo di creazione dei loop, viene assegnato un parametro N e il metodo crea quindi N di questi loop nidificati uno nell'altro?
Naturalmente, l'idea è che ci dovrebbe essere un " facile " o " il solito " modo di farlo. Ne ho già un'idea per una molto complicata.
Soluzione
Sembra che potresti voler esaminare ricorsione.
Altri suggerimenti
jjnguy ha ragione; la ricorsione ti consente di creare dinamicamente nidificazioni a profondità variabile. Tuttavia, non puoi accedere ai dati dai livelli esterni senza un po 'più di lavoro. & Quot; in-line-nested & Quot; caso:
for (int i = lo; i < hi; ++i) {
for (int j = lo; j < hi; ++j) {
for (int k = lo; k < hi; ++k) {
// do something **using i, j, and k**
}
}
}
mantiene le variabili i, j e k nell'ambito da utilizzare per il corpo più interno.
Ecco un trucco rapido per farlo:
public class NestedFor {
public static interface IAction {
public void act(int[] indices);
}
private final int lo;
private final int hi;
private final IAction action;
public NestedFor(int lo, int hi, IAction action) {
this.lo = lo;
this.hi = hi;
this.action = action;
}
public void nFor (int depth) {
n_for (0, new int[0], depth);
}
private void n_for (int level, int[] indices, int maxLevel) {
if (level == maxLevel) {
action.act(indices);
} else {
int newLevel = level + 1;
int[] newIndices = new int[newLevel];
System.arraycopy(indices, 0, newIndices, 0, level);
newIndices[level] = lo;
while (newIndices[level] < hi) {
n_for(newLevel, newIndices, maxLevel);
++newIndices[level];
}
}
}
}
L'interfaccia IAction stabilisce il ruolo di un'azione controllata che accetta una matrice di indici come argomento per il suo metodo act.
In questo esempio, ogni istanza di NestedFor è configurata dal costruttore con i limiti di iterazione e l'azione che deve essere eseguita dal livello più interno. Il parametro del metodo nFor specifica la profondità della nidificazione.
Ecco un esempio di utilizzo:
public static void main(String[] args) {
for (int i = 0; i < 4; ++i) {
final int depth = i;
System.out.println("Depth " + depth);
IAction testAction = new IAction() {
public void act(int[] indices) {
System.out.print("Hello from level " + depth + ":");
for (int i : indices) { System.out.print(" " + i); }
System.out.println();
}
};
NestedFor nf = new NestedFor(0, 3, testAction);
nf.nFor(depth);
}
}
e l'output (parziale) dalla sua esecuzione:
Depth 0
Hello from level 0:
Depth 1
Hello from level 1: 0
Hello from level 1: 1
Hello from level 1: 2
Depth 2
Hello from level 2: 0 0
Hello from level 2: 0 1
Hello from level 2: 0 2
Hello from level 2: 1 0
Hello from level 2: 1 1
Hello from level 2: 1 2
Hello from level 2: 2 0
Hello from level 2: 2 1
Hello from level 2: 2 2
Depth 3
Hello from level 3: 0 0 0
Hello from level 3: 0 0 1
Hello from level 3: 0 0 2
Hello from level 3: 0 1 0
...
Hello from level 3: 2 1 2
Hello from level 3: 2 2 0
Hello from level 3: 2 2 1
Hello from level 3: 2 2 2
Potresti voler spiegare cosa vuoi veramente fare.
Se i loop for esterni non fanno altro che controllare un conteggio, i loop <=> nidificati sono semplicemente un modo più complicato di iterare con un conteggio che può essere gestito da un singolo ciclo <=>.
Ad esempio:
for (x = 0; x < 10; ++x) {
for (y = 0; y < 5; ++y) {
for (z = 0; z < 20; ++z) {
DoSomething();
}
}
}
È equivalente a:
for (x = 0; x < 10*5*20; ++x) {
DoSomething();
}
In realtà stavo pensando a questo l'altro giorno.
Un esempio che probabilmente non è perfetto ma abbastanza vicino a quello che penso venga chiesto sarebbe la stampa di un albero di directory
public void printTree(directory) {
for(files in directory) {
print(file);
if(file is directory) {
printTree(file);
}
}
}
in questo modo finisci con una pila di loop annidati l'uno dentro l'altro, senza il fastidio di capire esattamente come dovrebbero andare insieme.
Modifica 2015: lungo lo stesso vano dell'incantesimo precedente, ho realizzato il seguente pacchetto per gestirlo; https://github.com/BeUndead/NFor
L'uso sarebbe il seguente
public static void main(String... args) {
NFor<Integer> nfor = NFor.of(Integer.class)
.from(0, 0, 0)
.by(1, 1, 1)
.to(2, 2, 3);
for (Integer[] indices : nfor) {
System.out.println(java.util.Arrays.toString(indices));
}
}
risultante
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]
Supporta anche condizioni diverse da lessThan. L'uso in corso (con import static NFor.*;):
NFor<Integer> nfor = NFor.of(Integer.class)
.from(-1, 3, 2)
.by(1, -2, -1)
.to(lessThanOrEqualTo(1), greaterThanOrEqualTo(-1), notEqualTo(0));
Risultato:
[-1, 3, 2]
[-1, 3, 1]
[-1, 1, 2]
[-1, 1, 1]
[-1, -1, 2]
[-1, -1, 1]
[0, 3, 2]
[0, 3, 1]
[0, 1, 2]
[0, 1, 1]
[0, -1, 2]
[0, -1, 1]
[1, 3, 2]
[1, 3, 1]
[1, 1, 2]
[1, 1, 1]
[1, -1, 2]
[1, -1, 1]
Ovviamente, sono supportati loop di lunghezze e classi diverse (tutte in box, primitive numeriche). Il valore predefinito (se non specificato) è da (0, ...). Da (1, ...); ma è necessario specificare un (...).
Il file NForTest dovrebbe dimostrare diversi modi per usarlo.
La premessa di base di questo è semplicemente far avanzare gli "indici" ogni turno piuttosto che usare la ricorsione.
Il problema richiede maggiori specifiche. Forse la ricorsione ti aiuterà, ma tieni presente che la ricorsione è quasi sempre un'alternativa all'iterazione e viceversa. È possibile che un ciclo nidificato a 2 livelli possa essere sufficiente per le tue esigenze. Facci sapere quale problema stai cercando di risolvere.
L'idea essenziale dietro i cicli di nidificazione è moltiplicazione .
Espandendosi sulla risposta di Michael Burr, se i cicli for esterni non fanno altro che controllare un conteggio, i tuoi cicli n nidificati su X sono semplicemente un modo più complicato di iterare sul prodotto dei conteggi con un singolo Y loop.
Ora estendiamo questa idea agli Elenchi. Se stai iterando su tre elenchi in loop nidificati, questo è semplicemente un modo più complicato di iterare il prodotto degli elenchi con un singolo loop. Ma come si esprime il prodotto di tre elenchi?
Innanzitutto, abbiamo bisogno di un modo per esprimere il prodotto dei tipi. Il prodotto di due tipi P2<X, Y> e P3<A, B, C> può essere espresso come un tipo generico come List<X>. Questo è solo un valore costituito da due valori, uno di tipo List<Y>, l'altro di tipo List<Z>. Sembra così:
public abstract class P2<A, B> {
public abstract A _p1();
public abstract B _p2();
}
Per un prodotto di tre tipi, abbiamo solo List<P3<X, Y, Z>>, con l'ovvio terzo metodo. Un prodotto di tre liste, quindi, si ottiene distribuendo il funzione Elenco sul tipo di prodotto. Quindi il prodotto di List, doSomething e <=> è semplicemente <=>. Puoi quindi scorrere su questo elenco con un singolo ciclo.
La Java funzionale ha un tipo <=> che supporta la moltiplicazione di elenchi utilizzando funzioni e tipi di prodotti di prima classe (P2, P3, ecc. Che sono anche inclusi nella libreria).
Ad esempio:
for (String x : xs) {
for (String y : ys) {
for (String z : zs) {
doSomething(x, y, z);
}
}
}
È equivalente a:
for (P3<String, String, String> p : xs.map(P.p3()).apply(ys).apply(zs)) {
doSomething(p._1(), p._2(), p._3());
}
Andando oltre con Functional Java, puoi creare <=> di prima classe, come segue. Diciamo che <=> restituisce una stringa:
public static final F<P3<String, String, String>, String> doSomething =
new F<P3<String, String, String>, String>() {
public String f(final P3<String, String, String> p) {
return doSomething(p._1(), p._2(), p._3());
}
};
Quindi puoi eliminare del tutto il for-loop e raccogliere i risultati di tutte le applicazioni di <=>:
List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);
Se si ha una struttura generale ad anello nidificato come:
for(i0=0;i0<10;i0++)
for(i1=0;i1<10;i1++)
for(i2=0;i2<10;i2++)
....
for(id=0;id<10;id++)
printf("%d%d%d...%d\n",i0,i1,i2,...id);
dove i0,i1,i2,...,id sono variabili del ciclo e d è la profondità del ciclo nidificato.
Soluzione di ricorsione equivalente:
void nestedToRecursion(counters,level){
if(level == d)
computeOperation(counters,level);
else
{
for (counters[level]=0;counters[level]<10;counters[level]++)
nestedToRecursion(counters,level+1);
}
}
void computeOperation(counters,level){
for (i=0;i<level;i++)
printf("%d",counters[i]);
printf("\n");
}
contatori è un array di dimensioni i0,i1,i2,...id, che rappresenta le variabili corrispondenti int counters[d] rispettivamente initial[d], ending[d].
nestedToRecursion(counters,0);
Allo stesso modo possiamo convertire altre variabili come l'inizializzazione della ricorsione o la fine usando array per loro, cioè potremmo avere <=>.
L'approccio generale più accurato che potrei trovare in Java 7 è
// i[0] = 0..1 i[1]=0..3, i[2]=0..4
MultiForLoop.loop( new int[]{2,4,5}, new MultiForLoop.Callback() {
void act(int[] i) {
System.err.printf("%d %d %d\n", i[0], i[1], i[2] );
}
}
O in Java 8:
// i[0] = 0..1 i[1]=0..3, i[2]=0..4
MultiForLoop.loop( new int[]{2,4,5},
i -> { System.err.printf("%d %d %d\n", i[0], i[1], i[2]; }
);
Un'implementazione che supporta questo è:
/**
* Uses recursion to perform for-like loop.
*
* Usage is
*
* MultiForLoop.loop( new int[]{2,4,5}, new MultiForLoop.Callback() {
* void act(int[] indices) {
* System.err.printf("%d %d %d\n", indices[0], indices[1], indices[2] );
* }
* }
*
* It only does 0 - (n-1) in each direction, no step or start
* options, though they could be added relatively trivially.
*/
public class MultiForLoop {
public static interface Callback {
void act(int[] indices);
}
static void loop(int[] ns, Callback cb) {
int[] cur = new int[ns.length];
loop(ns, cb, 0, cur);
}
private static void loop(int[] ns, Callback cb, int depth, int[] cur) {
if(depth==ns.length) {
cb.act(cur);
return;
}
for(int j = 0; j<ns[depth] ; ++j ) {
cur[depth]=j;
loop(ns,cb, depth+1, cur);
}
}
}
String fors(int n){
StringBuilder bldr = new StringBuilder();
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
bldr.append('\t');
}
bldr.append("for() {\n");
}
for(int i = n-1; i >= 0; i--){
for(int j = 0; j < i; j++){
bldr.append('\t');
}
bldr.append("}\n");
}
return bldr.toString();
}
Crea uno scheletro nidificato for-loop ;-) Non del tutto serio e sono consapevole che una soluzione ricorsiva sarebbe stata più elegante.
public void recursiveFor(Deque<Integer> indices, int[] ranges, int n) {
if (n != 0) {
for (int i = 0; i < ranges[n-1]; i++) {
indices.push(i);
recursiveFor(indices, ranges, n-1);
indices.pop();
}
}
else {
// inner most loop body, access to the index values thru indices
System.out.println(indices);
}
}
Chiamata di esempio:
int[] ranges = {2, 2, 2};
recursiveFor(new ArrayDeque<Integer>(), ranges, ranges.length);
la prima volta che ho risposto a una domanda, ma mi sentivo come se avessi bisogno di condividere queste informazioni di `
for (x = 0; x < base; ++x) {
for (y = 0; y < loop; ++y) {
DoSomething();
}
}
equivalente a
for (x = 0; x < base*loop; ++x){
DoSomething();
}
quindi se volevi un numero n di nidi, può essere scritto usando la divisione tra base e loop in modo che possa sembrare qualcosa di così semplice:
char[] numbs = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public void printer(int base, int loop){
for (int i = 0; i < pow(base, loop); i++){
int remain = i;
for (int j = loop-1; j >= 0; j--){
int digit = remain/int(pow(base, j));
print(numbs[digit]);
remain -= digit*pow(base, j);
}
println();
}
}
quindi se dovessi digitare printer(10, 2); verrebbe stampato:
00
01
02
03
04
...
97
98
99
Questo per me ha funzionato davvero bene - ho dovuto scegliere tra alcune alternative, che erano memorizzate in myAlternativePaths e l'idea di base è che stavo cercando di costruire la prossima selezione, e quando c'era un " overflow quot; in una dimensione / componente, devi solo reinizializzare quella dimensione e aggiungerne una alla successiva.
public boolean isValidAlternativeSelection (int[] alternativesSelected) {
boolean allOK = true;
int nPaths= myAlternativePaths.size();
for (int i=0; i<nPaths; i++) {
allOK=allOK & (alternativesSelected[i]<myAlternativePaths.get(i).myAlternativeRoutes.size());
}
return allOK;
}
public boolean getNextValidAlternativeSelection (int[] alternativesSelected) {
boolean allOK = true;
int nPaths= myAlternativePaths.size();
alternativesSelected[0]=alternativesSelected[0]+1;
for (int i=0; i<nPaths; i++) {
if (alternativesSelected[i]>=myAlternativePaths.get(i).myAlternativeRoutes.size()) {
alternativesSelected[i]=0;
if(i<nPaths-1) {
alternativesSelected[i+1]=alternativesSelected[i+1]+1;
} else {
allOK = false;
}
}
// allOK=allOK & (alternativesSelected[i]<myAlternativePaths.get(i).myAlternativeRoutes.size());
}
return allOK;
}
Nell'interesse della concisione sto inserendo il mio codice qui:
void variDepth(int depth, int n, int i) {
cout<<"\n d = "<<depth<<" i = "<<i;
if(!--depth) return;
for(int i = 0;i<n;++i){
variDepth(depth,n,i);
}
}
void testVariDeapth()
{ variDeapth(3, 2,0);
}
Output
d = 3 i = 0
d = 2 i = 0
d = 1 i = 0
d = 1 i = 1
d = 2 i = 1
d = 1 i = 0
d = 1 i = 1
