Если Вы добавляете в наборах, можно использовать сортировку слиянием. Отсортируйте список объектов, которые будут добавлены, затем скопируют с обоих списков, сравнивая объекты для определения, какой копируется затем. Вы могли даже скопировать оперативный, если изменяют размеры Вашего целевого массива и работы от конца назад.
эффективность этого решения является O (n+m) + O (m, регистрируют m), где n является размером исходного списка, и m является количеством вставляемых объектов.
Редактирование: , Так как этот ответ не получает любви, я думал, что буду конкретизировать его с некоторым примером кода C++. Я предполагаю, что отсортированный список сохранен в связанном списке, а не массиве. Это изменяет алгоритм для больше сходства на вставку, чем слияние, но принцип является тем же.
// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
std::sort(itemstoadd.begin(), itemstoadd.end());
std::list<T>::iterator listposition = sortedlist.begin();
std::vector<T>::iterator nextnewitem = itemstoadd.begin();
while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
{
if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
sortedlist.insert(listposition, *nextnewitem++);
else
++listposition;
}
}
Вот как я бы это настроил (в вашем models.py
)
class Member(models.Model):
name = models.CharField(max_length=100)
...
def __unicode__(self):
return self.name
class Band(models.Model):
name = models.CharField(max_length=100)
members = models.ManyToManyField(Member)
...
def __unicode__(self):
return self.name
class Song(models.Model):
name = models.CharField(max_length=100)
band = models.ForeignKey(Band)
...
def __unicode__(self):
return self.name
Настройте так:
member.band_set.all ()
дает вам все группы, к которым принадлежит участник band.members.all ()
дает вам участников группы song.band
дает вам группу для этой песни band .song_set.all ()
дает вам все песни для группы Обратите внимание, что band_set
на члене и song_set
на группе являются «обратными» отношениями. Они не определены явно в моделях, но Django настраивает их для вас прозрачно. Их можно настроить с помощью параметра related_name
в определении поля. Пример:
class Band(models.Model):
members = models.ManyToManyField(Member,related_name='bands')
позволит вам получить все группы для участника следующим образом:
member.bands.all()
Администратор автоматически предоставит следующее:
Однако, если вы хотите увидеть песни для группы, вам нужно будет сделать небольшая настройка администратора.
В вашем admin.py
:
from django.contrib import admin
class SongInline(admin.StackedInline):
model = Song
extra = 1
class BandAdmin(admin.ModelAdmin):
inlines = [SongInline]
admin.site.register(Band,BandAdmin)
admin.site.register(Member)
admin.site.register(Song)
Это позволит вам просматривать песни прямо со страницы администратора - а также редактировать или добавлять их! Следуя этому шаблону, вы также можете показать все группы для участника.
Вы можете получить более подробную информацию о настройке администратора на http://docs.djangoproject.com/en/dev/intro/tutorial02 /
Это все довольно просто. Я использовал описательные имена ниже, чтобы упростить понимание.
class Band(models.Model):
name = models.CharField(max_length=255)
class BandMember(models.Model):
name = models.CharField(max_length=255)
bands = models.ManyToManyField(Band)
class Song(models.Model):
name = models.CharField(max_length=255)
band = models.ForeignKey(Band)
# get a band
myband = Band.objects.get(name='myband')
# all songs from that band
print myband.song_set.all()
# all members of that band
print myband.bandmembers.all()
# get a specific band member
dave = BandMember.objects.get(name='Dave')
# what bands is Dave a member of?
print dave.bands.all()
# what songs has Dave sung? (slightly more complicated)
print Song.objects.get(band__bandmember=dave)