Erlang list和map的比较

原创
2021/12/11 19:40
阅读数 243

最佳实践

  • 比如排行榜数据,涉及到同一个玩家多次数据的更新,可以使用map来处理

此处存疑

  • 在maps_get的处理中,如果检测到maps不是flatmap,则执行的是1的插入,如果不是,则执行遍历的方式,那怎么判断maps是不是flatmap呢,或者什么样的maps是flatmap呢

#define MAP_HEADER_TAG_FLATMAP_HEAD (0x0) #define _HEADER_ARITY_OFFS 6

从数据更新上来看

  • maps是通过c实现的maps查找,最快替换效率是1,最慢是整个maps列表
  • list只能通过erlang的便利来更新,最优是使用lists:keytake来实现
// map的插入设置
Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map) {
    Uint32 hx;
    Eterm res;
    if (is_flatmap(map)) {
	Sint n,i;
	Sint c = 0;
	Eterm* hp, *shp;
	Eterm *ks, *vs, tup;
	flatmap_t *mp = (flatmap_t*)flatmap_val(map);

	n = flatmap_get_size(mp);

	if (n == 0) {
	    hp    = HAlloc(p, MAP_HEADER_FLATMAP_SZ + 1 + 2);
	    tup   = make_tuple(hp);
	    *hp++ = make_arityval(1);
	    *hp++ = key;
	    res   = make_flatmap(hp);
	    *hp++ = MAP_HEADER_FLATMAP;
	    *hp++ = 1;
	    *hp++ = tup;
	    *hp++ = value;

	    return res;
	}

	ks = flatmap_get_keys(mp);
	vs = flatmap_get_values(mp);

	/* only allocate for values,
	 * assume key-tuple will be intact
	 */

	hp  = HAlloc(p, MAP_HEADER_FLATMAP_SZ + n);
	shp = hp; /* save hp, used if optimistic update fails */
	res = make_flatmap(hp);
	*hp++ = MAP_HEADER_FLATMAP;
	*hp++ = n;
	*hp++ = mp->keys;

	if (is_immed(key)) {
	    for( i = 0; i < n; i ++) {
		if (ks[i] == key) {
                    goto found_key;
		} else {
		    *hp++ = *vs++;
		}
	    }
	} else {
	    for( i = 0; i < n; i ++) {
		if (EQ(ks[i], key)) {
		    goto found_key;
		} else {
		    *hp++ = *vs++;
		}
	    }
	}

	/* the map will grow */

	if (n >= MAP_SMALL_MAP_LIMIT) {
            ErtsHeapFactory factory;
	    HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp);
	    ks = flatmap_get_keys(mp);
	    vs = flatmap_get_values(mp);

            erts_factory_proc_init(&factory, p);
	    res = erts_hashmap_from_ks_and_vs_extra(&factory,ks,vs,n,key,value);
            erts_factory_close(&factory);

	    return res;
	}

	/* still a small map. need to make a new tuple,
	 * use old hp since it needs to be recreated anyway. */

	tup    = make_tuple(shp);
	*shp++ = make_arityval(n+1);

	hp    = HAlloc(p, 3 + n + 1);
	res   = make_flatmap(hp);
	*hp++ = MAP_HEADER_FLATMAP;
	*hp++ = n + 1;
	*hp++ = tup;

	ks = flatmap_get_keys(mp);
	vs = flatmap_get_values(mp);

	ASSERT(n >= 0);

	/* copy map in order */
	while (n && ((c = CMP_TERM(*ks, key)) < 0)) {
	    *shp++ = *ks++;
	    *hp++  = *vs++;
	    n--;
	}

	*shp++ = key;
	*hp++  = value;

	ASSERT(n >= 0);

	while(n--) {
	    *shp++ = *ks++;
	    *hp++  = *vs++;
	}
	/* we have one word remaining
	 * this will work out fine once we get the size word
	 * in the header.
	 */
	*shp = make_pos_bignum_header(0);
	return res;

found_key:
        if(*vs == value) {
            HRelease(p, shp + MAP_HEADER_FLATMAP_SZ + n, shp);
            return map;
        } else {
            *hp++ = value;
            vs++;
            if (++i < n)
               sys_memcpy(hp, vs, (n - i)*sizeof(Eterm));
            return res;
        }
    }
    ASSERT(is_hashmap(map));

    hx  = hashmap_make_hash(key);
    res = erts_hashmap_insert(p, hx, key, value, map, 0);
    ASSERT(is_hashmap(res));

    return res;
}

从数据通过key值查找来看

  • record的list可以提供多种灵活的多字段查询,查询效率最快是1,最慢是整个单链表的长度
  • maps的通过key来查找,查询效率最快也是1,最慢是整个数组的长度,只能对单个key进行查找
// 列表的源码查找
static Eterm
keyfind(int Bif, Process* p, Eterm Key, Eterm Pos, Eterm List)
{
    int max_iter = 10 * CONTEXT_REDS;
    Sint pos;
    Eterm term;

    if (!is_small(Pos) || (pos = signed_val(Pos)) < 1) {
	BIF_ERROR(p, BADARG);
    }

    if (is_small(Key)) {
	double float_key = (double) signed_val(Key);

	while (is_list(List)) {
	    if (--max_iter < 0) {
		BUMP_ALL_REDS(p);
		BIF_TRAP3(bif_export[Bif], p, Key, Pos, List);
	    }
	    term = CAR(list_val(List));
	    List = CDR(list_val(List));
	    if (is_tuple(term)) {
		Eterm *tuple_ptr = tuple_val(term);
		if (pos <= arityval(*tuple_ptr)) {
		    Eterm element = tuple_ptr[pos];
		    if (Key == element) {
			return term;
		    } else if (is_float(element)) {
			FloatDef f;

			GET_DOUBLE(element, f);
			if (f.fd == float_key) {
			    return term;
			}
		    }
		}
	    }
	}
    } else if (is_immed(Key)) {
	while (is_list(List)) {
	    if (--max_iter < 0) {
		BUMP_ALL_REDS(p);
		BIF_TRAP3(bif_export[Bif], p, Key, Pos, List);
	    }
	    term = CAR(list_val(List));
	    List = CDR(list_val(List));
	    if (is_tuple(term)) {
		Eterm *tuple_ptr = tuple_val(term);
		if (pos <= arityval(*tuple_ptr)) {
		    Eterm element = tuple_ptr[pos];
		    if (Key == element) {
			return term;
		    }
		}
	    }
	}
    } else {
	while (is_list(List)) {
	    if (--max_iter < 0) {
		BUMP_ALL_REDS(p);
		BIF_TRAP3(bif_export[Bif], p, Key, Pos, List);
	    }
	    term = CAR(list_val(List));
	    List = CDR(list_val(List));
	    if (is_tuple(term)) {
		Eterm *tuple_ptr = tuple_val(term);
		if (pos <= arityval(*tuple_ptr)) {
		    Eterm element = tuple_ptr[pos];
		    if (CMP_EQ(Key, element)) {
			return term;
		    }
		}
	    }
	}
    }

    if (is_not_nil(List))  {
	BIF_ERROR(p, BADARG);
    }
    return am_false;
}

// map 的查找算法
const Eterm *
erts_maps_get(Eterm key, Eterm map)
{
    Uint32 hx;
    if (is_flatmap(map)) {
	Eterm *ks, *vs;
	flatmap_t *mp;
	Uint n, i;

	mp  = (flatmap_t *)flatmap_val(map);
	n   = flatmap_get_size(mp);

	if (n == 0) {
	    return NULL;
	}

	ks  = (Eterm *)tuple_val(mp->keys) + 1;
	vs  = flatmap_get_values(mp);

	if (is_immed(key)) {
	    for (i = 0; i < n; i++) {
		if (ks[i] == key) {
		    return &vs[i];
		}
	    }
	} else {
            for (i = 0; i < n; i++) {
                if (EQ(ks[i], key)) {
                    return &vs[i];
                }
            }
        }
	return NULL;
    }
    ASSERT(is_hashmap(map));
    hx = hashmap_make_hash(key);

    return erts_hashmap_get(hx, key, map);
}
展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部
返回顶部
顶部