1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
<?xml version="1.0" encoding="utf-8"?>
<page xmlns="http://projectmallard.org/1.0/" xmlns:its="http://www.w3.org/2005/11/its" xmlns:xi="http://www.w3.org/2003/XInclude" type="topic" id="glist" xml:lang="es">
<info>
<link type="guide" xref="index#specific-how-tos"/>
<credit type="author copyright">
<name>Philip Withnall</name>
<email its:translate="no">philip.withnall@collabora.co.uk</email>
<years>2015</years>
</credit>
<include xmlns="http://www.w3.org/2001/XInclude" href="cc-by-sa-3-0.xml"/>
<desc>Listas enlazadas y tipos de contenedores</desc>
<mal:credit xmlns:mal="http://projectmallard.org/1.0/" type="translator copyright">
<mal:name>Daniel Mustieles</mal:name>
<mal:email>daniel.mustieles@gmail.com</mal:email>
<mal:years>2016-2020</mal:years>
</mal:credit>
<mal:credit xmlns:mal="http://projectmallard.org/1.0/" type="translator copyright">
<mal:name>Javier Mazorra</mal:name>
<mal:email>mazi.debian@gmail.com</mal:email>
<mal:years>2016, 2020</mal:years>
</mal:credit>
</info>
<title>GList</title>
<section id="glist-usage">
<title>Uso de GList</title>
<p>
GLib provides several container types for sets of data:
<link href="https://developer.gnome.org/glib/stable/glib-Doubly-Linked-Lists.html"><code>GList</code></link>,
<link href="https://developer.gnome.org/glib/stable/glib-Singly-Linked-Lists.html"><code>GSList</code></link>,
<link href="https://developer.gnome.org/glib/stable/glib-Pointer-Arrays.html"><code>GPtrArray</code></link> and
<link href="https://developer.gnome.org/glib/stable/glib-Arrays.html"><code>GArray</code></link>.
</p>
<p>
It has been common practice in the past to use GList in all situations
where a sequence or set of data needs to be stored. This is inadvisable —
in most situations, a GPtrArray should be used instead. It has lower
memory overhead (a third to a half of an equivalent list), better cache
locality, and the same or lower algorithmic complexity for all common
operations. The only typical situation where a GList may be more
appropriate is when dealing with ordered data, which requires expensive
insertions at arbitrary indexes in the array.
</p>
<p>
If linked lists are used, be careful to keep the complexity of operations
on them low, using standard CS complexity analysis. Any operation which
uses
<link href="https://developer.gnome.org/glib/2.30/glib-Doubly-Linked-Lists.html#g-list-nth"><code>g_list_nth()</code></link> or
<link href="https://developer.gnome.org/glib/2.30/glib-Doubly-Linked-Lists.html#g-list-nth-data"><code>g_list_nth_data()</code></link>
is almost certainly wrong. For example, iteration over a GList should be
implemented using the linking pointers, rather than a incrementing index:
</p>
<code mime="text/x-csrc" style="valid">GList *some_list, *l;
for (l = some_list; l != NULL; l = l->next)
{
gpointer element_data = l->data;
/* Do something with @element_data. */
}</code>
<p>
Using an incrementing index instead results in a quadratic decrease in
performance (<em>O(N^2)</em> rather than <em>O(N)</em>):
</p>
<code mime="text/x-csrc" style="invalid">GList *some_list;
guint i;
/* This code is inefficient and should not be used in production. */
for (i = 0; i < g_list_length (some_list); i++)
{
gpointer element_data = g_list_nth_data (some_list, i);
/* Do something with @element_data. */
}</code>
<p>
The performance penalty comes from <code>g_list_length()</code> and
<code>g_list_nth_data()</code> which both traverse the list
(<em>O(N)</em>) to perform their operations.
</p>
<p>La implementación de lo anterior con un GPtrArray tiene la misma complejidad que la primera implementación GList (correcta), pero mejor localidad de caché y menor consumo de memoria, por lo que funcionará mejor para un gran número de elementos:</p>
<code mime="text/x-csrc" style="valid">GPtrArray *some_array;
guint i;
for (i = 0; i < some_array->len; i++)
{
gpointer element_data = some_array->pdata[i];
/* Do something with @element_data. */
}</code>
</section>
</page>
|
