多维数据遍历

在联机分析处理（OLAP）系统中，需要对存储在数据库或数据仓库中的数据提供分析。由于数据维数不定，无法采用多重for循环进行数据遍历。我在开发过程中一般使用扁平化下标对多维数据进行遍历，今天尝试了一下递归方式，效率更高一些，但是对栈的消耗也更多一些。下面的代码示例使用两种不同的方式对多维数据进行遍历：

• 递归
• 采用扁平化下标

示例代码

package com.yqu.collection;

import java.util.ArrayList;

import java.util.List;

public class MultipleDimensionTraveling <T>{

  private List<List<T>> mdList;

  public MultipleDimensionTraveling(){
    mdList = new ArrayList<List<T>>();
  }

  public MultipleDimensionTraveling(List<List<T>> mdList){
    this.mdList = mdList;
  }

  public void addDimension(List<T> dim){
    mdList.add(dim);
  }

  public void travelByRecursion(){
    if(!mdList.isEmpty())
      travelByRecursion(0, new ArrayList<T>(mdList.size()));
  }

  private void travelByRecursion(int dimIdx, List<T> crossing){
    for(int i=0;i<mdList.get(dimIdx).size();i++){
      if(crossing.size()<mdList.size())
        crossing.add(dimIdx, mdList.get(dimIdx).get(i));
      else
        crossing.set(dimIdx, mdList.get(dimIdx).get(i));

      if(dimIdx==mdList.size()-1){
          System.out.println(crossing.toString());
      } else {
          travelByRecursion(dimIdx+1, crossing);
      }
    }
  }

  public void travelByFlatIndice(){
    if(!mdList.isEmpty()){
      int crossingNum = 1;
      int[] cardinalities = new int[mdList.size()];
      int[] multipliers = new int[mdList.size()];

      for(int i=0;i<mdList.size();i++) {
        List<T> dim = mdList.get(i);
        cardinalities[i] = dim.size();
        crossingNum *= cardinalities[i];
      }

      for(int i=cardinalities.length-1;i>=0;i--) {
        multipliers[i] = (i == multipliers.length - 1)?
            1 : cardinalities[i+1]*multipliers[i+1];
      }

      for(int flatIndice=0;flatIndice<crossingNum;flatIndice++){
        handleCrossing(flatIndice, multipliers);
      }
    }
  }

  private void handleCrossing(int flatIndice, int[] multipliers){
    List<T> crossing = new ArrayList<T>(multipliers.length);
      for (int dimIdx = 0; dimIdx < multipliers.length; dimIdx++){
        int mbrIdx = flatIndice / multipliers[dimIdx];
        crossing.add(dimIdx, mdList.get(dimIdx).get(mbrIdx));            
        flatIndice = flatIndice % multipliers[dimIdx];
      }
      System.out.println(crossing);
  }  

  public static void main(String[] args) {    
    MultipleDimensionTraveling<String> mdlObj = 
      new MultipleDimensionTraveling<String>();
    List<String> dim = new ArrayList<String>();
    dim.add("dim1A");
    dim.add("dim1B");
    dim.add("dim1C");
    mdlObj.addDimension(dim);

    dim = new ArrayList<String>();
    dim.add("dim2A");
    dim.add("dim2B");
    dim.add("dim2C");
    dim.add("dim2D");
    mdlObj.addDimension(dim);

    dim = new ArrayList<String>();
    dim.add("dim3A");
    dim.add("dim3B");
    mdlObj.addDimension(dim);

    System.out.println("Travling by flat indice:");
    mdlObj.travelByFlatIndice();
    System.out.println("Travling by recursion:");
    mdlObj.travelByRecursion();
  }
}

运行结果

Multiple dimension list travling by flat indice:
[dim1A, dim2A, dim3A]
[dim1A, dim2A, dim3B]
[dim1A, dim2B, dim3A]
[dim1A, dim2B, dim3B]
[dim1A, dim2C, dim3A]
[dim1A, dim2C, dim3B]
[dim1A, dim2D, dim3A]
[dim1A, dim2D, dim3B]
[dim1B, dim2A, dim3A]
[dim1B, dim2A, dim3B]
[dim1B, dim2B, dim3A]
[dim1B, dim2B, dim3B]
[dim1B, dim2C, dim3A]
[dim1B, dim2C, dim3B]
[dim1B, dim2D, dim3A]
[dim1B, dim2D, dim3B]
[dim1C, dim2A, dim3A]
[dim1C, dim2A, dim3B]
[dim1C, dim2B, dim3A]
[dim1C, dim2B, dim3B]
[dim1C, dim2C, dim3A]
[dim1C, dim2C, dim3B]
[dim1C, dim2D, dim3A]
[dim1C, dim2D, dim3B]
Multiple dimension list travling by recursion:
[dim1A, dim2A, dim3A]
[dim1A, dim2A, dim3B]
[dim1A, dim2B, dim3A]
[dim1A, dim2B, dim3B]
[dim1A, dim2C, dim3A]
[dim1A, dim2C, dim3B]
[dim1A, dim2D, dim3A]
[dim1A, dim2D, dim3B]
[dim1B, dim2A, dim3A]
[dim1B, dim2A, dim3B]
[dim1B, dim2B, dim3A]
[dim1B, dim2B, dim3B]
[dim1B, dim2C, dim3A]
[dim1B, dim2C, dim3B]
[dim1B, dim2D, dim3A]
[dim1B, dim2D, dim3B]
[dim1C, dim2A, dim3A]
[dim1C, dim2A, dim3B]
[dim1C, dim2B, dim3A]
[dim1C, dim2B, dim3B]
[dim1C, dim2C, dim3A]
[dim1C, dim2C, dim3B]
[dim1C, dim2D, dim3A]
[dim1C, dim2D, dim3B]