Реализация класса Tree Writable - PullRequest
Новая
       20

Реализация класса Tree Writable

1 голос
/ 05 марта 2011

Я хотел бы реализовать класс TreeWritable для представления структуры дерева. Я пробовал следующую реализацию, но я получаю mapred.MapTask: запись слишком велика для ошибки буфера в памяти. Как мне реализовать Writable для многоуровневой структуры данных? 

public class TreeWritable implements Writable
{
private final Set<TreeWritable> children = new LinkedHashSet<TreeWritable>();
private String data;
private int level;

public TreeWritable( String data, int level )
{
    this.data = data;
    this.level = level;
}

public int getLevel()
{
    return level;
}

public TreeWritable()
{
}

public TreeWritable child( String data )
{
    for ( TreeWritable child : children )
    {
        if ( child.data.equals( data ) )
        {
            return child;
        }
    }
    return child( new TreeWritable( data, this.level + 1 ) );
}

TreeWritable child( TreeWritable child )
{
    children.add( child );
    return child;
}

public Set<TreeWritable> getChildren()
{
    return children;
}

public String getId()
{
    return data;
}

public void write( DataOutput out ) throws IOException
{
    out.writeUTF( data );
    out.write( level );
    int size = children.size();
    out.writeInt( size );        
    while(children.iterator().hasNext())
        children.iterator().next().write( out );
}

public void readFields( DataInput in ) throws IOException
{
    data = in.readUTF();
    level = in.readInt();
    int size = in.readInt();
    for ( int i = 0; i < size; i++ )
        children.add( TreeWritable.read( in ) );
}

public static TreeWritable read( DataInput in ) throws IOException
{
    TreeWritable w = new TreeWritable();
    w.readFields( in );
    return w;
}
}

1 Ответ

1 голос
/ 05 марта 2011

Я думаю, что это оптимальная реализация небольших деревьев, если она предназначена для обработки на одной машине. Если вы работаете с большими деревьями, вы должны разбить его на части дерева и сохранить, например, в виде кортежей (id, data, root_id).

Другим примером структуры данных для оценки PageRank в MapReduce является (url, currentPageRank, [link_url1, link_url2, ...])

...